250 Points
枚舉每一個要求的數(shù)字，求它到左上角的最小步數(shù)即可。注意數(shù)字可以穿越邊界。
#define INF 1000000000
int n,m;
int cnt(int x,int y)
{
int res=INF;
if(abs(x)+abs(y)<res)
res=abs(x)+abs(y);
if(abs(n-x)+abs(m-y)<res)
res=abs(n-x)+abs(m-y);
if(abs(n-x)+abs(y)<res)
res=abs(n-x)+abs(y);
if(abs(x)+abs(m-y)<res)
res=abs(x)+abs(m-y);
return res;
}
class MatrixShiftings
{
public:
int minimumShifts(vector <string> matrix, int v)
{
n=matrix.size();
m=matrix[0].length();
int res=INF;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
if(matrix[i][j]-'0'==v)
if(cnt(i,j)<res)
res=cnt(i,j);
}
if(res==INF)
return -1;
else
return res;
}
};
500 Points
剛開始的時候以為是DP,一直在那里想狀態(tài)怎么表示，結果后來一個特例把DP給否決了，囧。。。
其實只要枚舉要選擇的個數(shù)，假設是N,然后把每個小動物的代價都算出來，排序，取最小的前N個之和，如果滿足要求，更新答案，不滿足就跳出。最近果然題目做少了啊，看到這種題都沒什么感覺，今天做華中科大的比賽也是如此，得多練啊，這種題靠的就是個感覺。
class Badgers
{
public:
int feedMost(vector <int> h, vector <int> g, int tol)
{
int n=h.size();
vector<int> tem;
tem.clear();
int i,j,k;
long long ans=0;
for(i=1;i<=n;i++)
{
tem.clear();
for(j=0;j<n;j++)
{
tem.push_back((h[j]+g[j]*(i-1)));
}
sort(tem.begin(),tem.end());
long long sum=0;
for(j=0;j<i;j++)
sum+=tem[j];
if(sum>tol)
{
return i-1;
}
}
return n;
}
};
1000 Points
動態(tài)規(guī)劃
一個串X是Y的subanagram ，即X中的所有字母在Y中出現(xiàn)過，而且不需要考慮位置關系。
設計狀態(tài)dp[i][j]如果大于零，說明s[i]-s[j]被單獨分成了一個部分，且dp[i][j]代表如果這樣分s[0-j]在滿足題意要求下可以被切割成的最大段數(shù)。枚舉每一種切割方式，最后在dp[i][n-1]中取最大值即可，復雜度應該是n^3。
這題在判斷一個串是否在另一個串中出現(xiàn)過的方法很好，學習了^_^
int const maxn=550;
int dp[maxn][maxn];
int w[50];
class SubAnagrams
{
public:
int maximumParts(vector <string> str)
{
string s;
s.clear();
for(int i=0;i<(int)str.size();i++)
s+=str[i];
int n=s.length();
int i,j,k;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
if(!i||dp[i][j]>0)
{
memset(w,0,sizeof(w));
int cnt=0;//記錄字母出現(xiàn)個數(shù)
for(k=i;k<=j;j++)
{
w[s[k]-'A']++;
if(w[s[k]-'A']==1)
cnt++;
}
for(k=j+1;j<n;j++)
{
w[s[k]-'A']--;
if(w[s[k]-'A']==0)
cnt--;
if(cnt==0)
dp[j+1][k]=max(dp[j+1][k],dp[i][j]+1);
}
}
}
}
int ans=0;
for(i=0;i<n;i++)
ans=max(ans,dp[i][n-1]);
return ans+1;
}
};