两道题都是结束以后才想出来。。。两题都只过了20%，哭了。
第一题应该是只有当所有数字都出现偶数次时候第二个人才能赢，其他情况都是第一个人赢。
第二题我以为是只能取每一层的一头一尾两个，写了一个dp，只过了20%，结束以后我发现数据给的n和c最大为100，m最大为10000，说明如果m >= n * c，所有物品都可以拿走，所以每一层如果已经拿了第1个和第c个，那就还可以继续拿第2个和第c-1个。
个人觉得是个背包dp，然后时间不够呀！！！
好气！结束了才想到。
（代码有问题。。。不好意思，我删掉重写）
昨晚躺在床上突然发现之前这样子贪心找到的并不是最优解，思来想去，发现可以用滑动窗口预处理出当前层取x个物品可以获得的最大价值存在数组中，然后dp，复杂度O(n*（c^2+m*c）)，我觉得应该没有问题，欢迎大家指正！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[110], val[110];
int dp[10010];
int main()
{
int n, m, c;
cin >> n >> m;
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++){
int sum = 0;//求当前层物品价值和
cin >> c;
for (int j = 0; j < c; j++){
cin >> a[j];
sum += a[j];
}
memset(val, 0, sizeof val);
for (int k = 1; k <= c; k++){ // 当前层获得k件物品可得的最大值存入val
int index = 0, now = 0;//滑动窗口，窗口大小为c-k
while (index < c-k){
now += a[index];
index++;
}
val[k] = max(val[k], sum-now);
while (index < c){
now += a[index];
now -= a[index-c+k];
val[k] = max(val[k], sum-now);
index++;
}
}
for (int j = m; j > 0; j--)
for (int k = 1; k <= min(j, c); k++)
dp[j] = max(dp[j], dp[j-k]+val[k]);
}
cout << dp[m] << endl;
return 0;
} 
全部评论
(17) 回帖