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排好序。

输出格式

对于每个用例，输出他能拿的最多的奖金。

样例输入

样例输出

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 ;

}

ZEH