2018年东北地区赛S - Problem I. Spell Boost HDU

题目地址：https://vjudge.net/problem/HDU-6508

思路：
给一些卡，分为四种卡。
1.白卡（没效果）
2.魔法，作用卡（会对作用卡的费用减少，也会被魔法卡作用）
3.作用卡（会被魔法卡作用使其费用减少）
4.魔法卡（会对作用卡的费用减少）

有一个想法：如果我们得到最大的攻击力，其中会用到魔法卡和作用卡或者两者效果都有的卡的话，魔法卡其实是越早用越好
，而作用卡越晚用晚用越好，因为作用卡会被魔法卡影响，使其费用减少，而且费用少的卡需要先使用，才能尝试更多的可能，
如果一张卡是10w，一张卡是1w，为了尝试更多可能，先让费用少的先尝试，（比如，先1w可以dp[1w],dp[1w+ 10w],但dp[10w]，之前没有dp[1w]）让费用多的之后对dp[N][N]进行比较。
那么，dp[N][N], 第一个维度为费用值，第二个维度为用了几张魔法卡，维护的是最大攻击力。
然后就是一个01背包问题，当然为了实现我们的想法，需要对结构体进行某些特定的排序。

补：其实可以这么想。我们打出了最好顺序情况的卡，那么我们的打出的卡中有其中几类的卡。那么，如果我们用了魔法卡，那我们一定先用魔法卡，用了作用卡，那么作用卡一定是之后用的，从最好的结果，来反推该背包该怎么dp，之后我看博客，想想这样更好理解，在这里补充一下。

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define rep(i,j,k) for(int i = (j); i <= (k); i++)

 #define per(i,j,k) for(int i = (j); i >= (k); i--)

 const int N = ;

 int dp[N][N];

 struct node{

     int w, x;

     int is_m, is_s;

     bool friend operator < (node a, node b){

         if (a.is_m != b.is_m) return a.is_m > b.is_m;//魔法卡先返回

         else if (a.is_s != b.is_s) return a.is_s < b.is_s;//作用卡越晚用越好

         return a.w < b.w;//先用费用小的，使其dp可以得到全部可能

     }

 };

 node arr[N];

 void init(int x){

 //    rep(i, 0, x)rep(j, 0, x) dp[i][j] = 0;

     memset(dp, , sizeof(dp));

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie();

     int n, W;

     while (cin >> n >> W){

         int m_num = ;

         rep(i, , n){

             cin >> arr[i].w >> arr[i].x >> arr[i].is_m >> arr[i].is_s;

             if (arr[i].is_m) ++m_num;//统计魔法卡数量

         }

         init(n);

         sort(arr + , arr +  + n);

         bool is_s = false;//判断是不是作用卡

         //从大到小遍历，可以不影响之前的状态

         rep(i, , n){

             if (arr[i].is_m){

                 per(k, i, ){//魔法卡从多到少

                     per(j, W, ){//费用从多到少

                         int tmp_w = ;

                         if (arr[i].is_s){//有被作用效果

                             is_s = true;

                             tmp_w = max(, arr[i].w - (k - ));//触发魔法卡效果

                         }

                         //对于k张魔法卡，之前只有k-1张魔法卡，假如一张魔法卡去更新dp,所以被作用时

                         //应该是魔法卡数量-1的费用减少

                         if (is_s && tmp_w <= j){//是作用卡，费用足够

                             dp[j][k] = max(dp[j][k],dp[j - tmp_w][k - ] + arr[i].x);

                         }

                         else if (!is_s && arr[i].w <= j){//不是作用卡，费用足够

                             dp[j][k] = max(dp[j][k], dp[j - arr[i].w][k - ] + arr[i].x);

                         }

                     }

                 }

             }

             else {

                 //进入该部分时，全部的魔法卡使用情况已经存入dp，之后的都不是魔法卡

                 per(k, m_num, ){//m_num是魔法卡总数量，可能有不用魔法卡才能的到最大攻击的情况

                     per(j, W, ){

                         int tmp_w = ;

                         if (arr[i].is_s){

                             is_s = true;

                             tmp_w = max(, arr[i].w - k);

                         }

                         //对于k张魔法卡，被作用卡卡费用减少k

                         if (is_s && tmp_w <= j){

                             dp[j][k] = max(dp[j][k], dp[j - tmp_w][k] + arr[i].x);

                         }

                         else if (!is_s && arr[i].w <= j){

                             dp[j][k] = max(dp[j][k], dp[j - arr[i].w][k] + arr[i].x);

                         }

                     }

                 }

             }

             is_s = false;

         }

         int ans = ;

         rep(i, , m_num) ans = max(ans, dp[W][i]);//遍历费用是W的dp最大值，即为最大攻击力

         cout << ans << endl;

     }

     return ;

 }

巴特西

2018年东北地区赛S - Problem I. Spell Boost HDU - 6508

题目地址：https://vjudge.net/problem/HDU-6508

最新文章

热门文章