两道dp

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

链接：https://ac.nowcoder.com/acm/contest/186/C?&headNav=www

来源：牛客网
终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）

题解：直接dp

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int a[];

 int dp[][];

 int main(){

     int n,m;

     cin>>n>>m;

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

     }

     memset(dp,-,sizeof(dp));

     for(int i=;i<=n;i++)dp[i][]=;

     for(int i=;i<=n;i++){

         for(int j=;j<=;j++){

             dp[i][j]=dp[i-][j];

             if(dp[i-][j-a[i]]!=-)dp[i][j]=max(dp[i-][j-a[i]]+a[i],dp[i][j]);

             if(dp[i-][j+a[i]]!=-)dp[i][j]=max(dp[i-][j+a[i]]+a[i],dp[i][j]);

         }

     }

     int ans=;

     for(int i=;i<=n;i++)

     for(int j=-m;j<=+m;j++){

         ans=max(ans,dp[i][j]);

     }

     cout<<ans<<endl;

     return ;

 }

http://www.hrbuacm.top/problem.php?id=5328

来源：东北四省赛

题意：给n张牌，总体力w，每张牌需要花费wi造成xi的伤害，同时每张牌可能会有两个属性，第一个属性可以在使用时使所有具有第二种属性的牌的w减1，计算最大伤害

样例输入

3 3
3 3 1 1
2 3 1 1
1 3 1 1

样例输出

9
思路：贪心+dp

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<set>

 #include<bitset>

 #include<vector>

 #include<map>

 using namespace std;

 typedef long long ll;

 const int maxn=;

 int dp[maxn][maxn],ak[maxn];

 struct pot{

     int a;

     int b;

     int c;

     int d;

 }p[maxn];

 bool cmp(struct pot aa,struct pot bb){

     if(aa.d==bb.d){

             if(aa.c==bb.c)

             return aa.a<bb.a;

             else return aa.c>bb.c;

         }

     return aa.d<bb.d;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie();

     cout.tie();

     int n,w;

     cin>>n>>w;

     for(int i=;i<=n;i++){

         cin>>p[i].a>>p[i].b>>p[i].c>>p[i].d;

     }

     int ans=;

     sort(p+,p++n,cmp);

     memset(dp,-,sizeof(dp));

     dp[][]=;

     for(int i=;i<=n;i++){ak[i]=ak[i-]+(p[i].c);}

     for(int i=;i<=n;i++){

         for(int j=i;j>=;j--){

             for(int k=w;k>=;k--){

                 if(p[i].c){

                     int xx=max(,p[i].a-j+);

                     if(k>=xx&&p[i].d&&j&&dp[j-][k-xx]!=-){

                             dp[j][k]=max(dp[j][k],dp[j-][k-xx]+p[i].b);

                     }

                     else if(k>=p[i].a&&j&&dp[j-][k-p[i].a]!=-)dp[j][k]=max(dp[j][k],dp[j-][k-p[i].a]+p[i].b);

                 }

                 else{

                     int xx=max(,p[i].a-j);

                     if(k>=xx&&p[i].d&&dp[j][k-xx]!=-){

                             dp[j][k]=max(dp[j][k],dp[j][k-xx]+p[i].b);

                     }

                     else if(k>=p[i].a&&dp[j][k-p[i].a]!=-)dp[j][k]=max(dp[j][k],dp[j][k-p[i].a]+p[i].b);

                 }

             ans=max(ans,dp[j][k]);

             }

         }

     }

     cout<<ans<<endl;

     return ;

 }