1750. 运动会
限制条件
时间限制: 1 秒, 内存限制: 32 兆
题目描述
ZEH是一名04级的学生，他除了绩点高，还有运动细胞。有一次学院举办运动会，ZEH发现里面的 项目都是他所向披靡的，当然他想获得所有项目的No1，但是一个人的精力总是有限的，ZEH也是只有P(Power的简写，一个大于0且小于1000的整 数)的精力。如果精力足够参加比赛，一定能赢；相反，精力不够去参加比赛，Loss的概率很大，ZEH当然不想因为Loss而不爽。
整个运动会有N(大于0且小于等于100)项比赛，每项比赛都是在指定的一天D(D大于等于0)内举行完，但是一天可能同时有多个比赛同时进 行，ZEH当然就不能同时兼顾。比赛结束后，院长都会亲自为冠军颁发一定数额的奖金，其他名次只有一张奖状。ZEH当然是冲着奖金去的，他想获得最多的奖 金，师弟师妹们，你能帮ZEH大牛计算出他最多能拿多少奖金吗？
输入格式
第一行是一个整数T，表示这题有T个用例。
每个用例的第一行有两个正整数P N，分别表示ZEH的精力和比赛的项目。
第二行到第N+1行是N个项目，每一行有三个正整数D E M，分别表示这个项目在第D天举行，需要E的精力，和比赛的奖金。项目的顺序都按D排好序。
输出格式
对于每个用例，输出他能拿的最多的奖金。
样例输入
1
14 5
0 3 7
0 2 5
1 4 2
2 6 14
2 8 15
样例输出
23 刚开始的时候用一维dp[]去做，死活过不了，找了很久也没有找到原因，如果有哪位大神刚好看见，可以帮帮我查错。
后来改用了二维的dp[][]做，顺利的AC。 这一题题目本身就有问题，提纲上说D是正整数，但是例子里面给的D第一个就为0，这个我们先不管，考虑题目本身。 题目本身就是一个典型的分组背包问题，首先，将给定的项目按天分组，用合适的数据结构存储起来。
然后，按0-1背包的做法对天数进行选择，再在每天里对当天的项目做一个重复比较，最后一天只选到一个项目，原理和0-1背包是一致的。 核心代码：
for(int i=;i<=D;i++){
if(xmP[i].size()==)
continue;
for(int j=P;j>=;j--){
if (i>)
dp[i][j]=dp[i-][j];
for(int k=;k<xmP[i].size();k++){
if(xmP[i][k]<=j){
if(i>)
dp[i][j]=max(dp[i][j],dp[i-][j-xmP[i][k]]+xmM[i][k]);
else
dp[i][j]=max(dp[i][j],dp[i][j-xmP[i][k]]+xmM[i][k]);
}
}
Max=max(Max,dp[i][j]);
}
}
对第0天的情况特殊处理了，还要注意dp[i][j]=max(dp[i][j],dp[i-1][j-xmP[i][k]]+xmM[i][k]);里的是dp[i][j]并不是dp[i-1][j]。
因为这里需要跟当天的上一个项目得出的结果做一个比较。
if (i>0)
dp[i][j]=dp[i-1][j];
已经进行了初始化,所以一开始进入k的循环dp[i][j]就是当天不选项目即dp[i-1][j]的情况。
附上全部代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<memory.h> using namespace std; int main()
{
int T,P,N,D,E,M;
int dp[][];
vector<int> xmP[];
vector<int> xmM[];
cin>>T;
while(T--){
cin>>P>>N;
for(int i=;i<;i++){
xmP[i].clear();
xmM[i].clear();
}
for(int i=;i<N;i++){
cin>>D>>E>>M;
xmP[D].push_back(E);
xmM[D].push_back(M);
}
memset(dp,,sizeof(dp));
int Max=;
for(int i=;i<=D;i++){
if(xmP[i].size()==)
continue;
for(int j=P;j>=;j--){
if (i>)
dp[i][j]=dp[i-][j];
for(int k=;k<xmP[i].size();k++){
if(xmP[i][k]<=j){
if(i>)
dp[i][j]=max(dp[i][j],dp[i-][j-xmP[i][k]]+xmM[i][k]);
else
dp[i][j]=max(dp[i][j],dp[i][j-xmP[i][k]]+xmM[i][k]);
}
}
Max=max(Max,dp[i][j]);
}
}
cout<<Max<<endl;
}
return ;
}