TC SRM 553 DIV2

赤裸裸的又在送rate。
250PT:
可以列个方程组，然后解方程，唯一解，也可以枚举两个，写得再烂再烂也有1000^2的上限，可以过。

500PT:
两种情况，一种是将-1置为0，然后判断是否能把最后一个数变为目标，如果可以的话，那么0肯定是最小的选择了。
另外就是直接模拟，然后判断最后一个数是否比目标小，如果比目标小的话，就可以把-1转变成那个差值-1。
貌似我还记录了在模拟的过程中，-1的位置，这个应该没有影响。。如果-1在前面的话，会在第一种情况就测试出。

1000PT:
哭 死，刚敲完就结束了，不应该尝试搜索和贪心的
贪心是有反例的，如果直接排序的话，那么
1 2 2 10
2
这组数据就过不了。
对于余数分为4组，然后再贪心也是错的
{1,101,105,6,10} 2， ORZ Dshawn神牛cha全场
正解是DP
同样对于余数进行分组，可以在每一组内贪心
dp[a][b][c][d]表示每一组分别取了a,b,c,d个的最优解
貌似还有种做法是dp[i][j][k] 前i个数字取掉j个余数是k
[cpp]
int dp[51][51][51][51]={0};
class SafeRemoval{
public:
int removeThem(vector seq, int k){
sort(seq.begin(),seq.end());
vectorv[4];
int n=seq.size();
int sum=0;
for(int i=0;i v[seq[i]%4].push_back(seq[i]);
sum+=seq[i];
}
memset(dp,-1,sizeof(dp));
dp[0][0][0][0]=sum;
for(int i=0;i for(int a=0;a<=v[0].size();a++){
for(int b=0;b<=v[1].size();b++){
for(int c=0;c<=v[2].size();c++){
for(int d=0;d<=v[3].size();d++){
if(dp[a][b][c][d]==-1) continue;
if(a+b+c+d>i) continue;
if(a dp[a+1][b][c][d]=max(dp[a][b][c][d]-v[0][a],dp[a+1][b][c][d]);
if(b dp[a][b+1][c][d]=max(dp[a][b][c][d]-v[1][b],dp[a][b+1][c][d]);
if(c dp[a][b][c+1][d]=max(dp[a][b][c][d]-v[2][c],dp[a][b][c+1][d]);
if(d dp[a][b][c][d+1]=max(dp[a][b][c][d]-v[3][d],dp[a][b][c][d+1]);
}
}
}
}
}
int ans=-1;
for(int a=0;a<=v[0].size();a++)
for(int b=0;b<=v[1].size();b++)
for(int c=0;c<=v[2].size();c++)
for(int d=0;d<=v[3].size();d++)
if(a+b+c+d==k)
ans=max(dp[a][b][c][d],ans);
return ans;
}
};