250 Points
枚举每一个要求的数字，求它到左上角的最小步数即可。注意数字可以穿越边界。
#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,一直在那里想状态怎么表示，结果后来一个特例把DP给否决了，囧。。。
其实只要枚举要选择的个数，假设是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
动态规划
一个串X是Y的subanagram ，即X中的所有字母在Y中出现过，而且不需要考虑位置关系。
设计状态dp[i][j]如果大于零，说明s[i]-s[j]被单独分成了一个部分，且dp[i][j]代表如果这样分s[0-j]在满足题意要求下可以被切割成的最大段数。枚举每一种切割方式，最后在dp[i][n-1]中取最大值即可，复杂度应该是n^3。
这题在判断一个串是否在另一个串中出现过的方法很好，学习了^_^
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;//记录字母出现个数
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;
}
};