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

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;  4 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
 5 #define per(i,k) for(int i = (j); i >= (k); i--)
 6 
 7 const int N = 510;  8 int dp[N][N];  9 
 10 struct node{  11     int w,x;  12     int is_m,is_s;  13 
 14     bool friend operator < (node a,node b){  15         if (a.is_m != b.is_m) return a.is_m > b.is_m;//魔法卡先返回
 16         else if (a.is_s != b.is_s) return a.is_s < b.is_s;//作用卡越晚用越好
 17 
 18         return a.w < b.w;//先用费用小的，使其dp可以得到全部可能
 19  }  20 };  21 
 22 node arr[N];  23 
 24 void init(int x){  25 // rep(i,x)rep(j,x) dp[i][j] = 0;
 26     memset(dp,0,sizeof(dp));  27 }  28 
 29 int main(){  30 
 31     ios::sync_with_stdio(false);  32     cin.tie(0);  33 
 34     int n,W;  35     while (cin >> n >> W){  36 
 37         int m_num = 0;  38 
 39         rep(i,1,n){  40             cin >> arr[i].w >> arr[i].x >> arr[i].is_m >> arr[i].is_s;  41             if (arr[i].is_m) ++m_num;//统计魔法卡数量
 42  }  43 
 44  init(n);  45 
 46         sort(arr + 1,arr + 1 + n);  47 
 48         bool is_s = false;//判断是不是作用卡  49         //从大到小遍历，可以不影响之前的状态
 50         rep(i,n){  51             if (arr[i].is_m){  52 
 53                 per(k,i,1){//魔法卡从多到少
 54                     per(j,W,0){//费用从多到少
 55 
 56                         int tmp_w = 0;  57                         if (arr[i].is_s){//有被作用效果
 58                             is_s = true;  59                             tmp_w = max(0,arr[i].w - (k - 1));//触发魔法卡效果
 60  }  61                         //对于k张魔法卡，之前只有k-1张魔法卡，假如一张魔法卡去更新dp,所以被作用时  62                         //应该是魔法卡数量-1的费用减少
 63                         if (is_s && tmp_w <= j){//是作用卡，费用足够
 64                             dp[j][k] = max(dp[j][k],dp[j - tmp_w][k - 1] + arr[i].x);  65  }  66                         else if (!is_s && arr[i].w <= j){//不是作用卡，费用足够
 67                             dp[j][k] = max(dp[j][k],dp[j - arr[i].w][k - 1] + arr[i].x);  68  }  69  }  70  }  71  }  72             else {  73                 //进入该部分时，全部的魔法卡使用情况已经存入dp，之后的都不是魔法卡
 74                 per(k,m_num,0){//m_num是魔法卡总数量，可能有不用魔法卡才能的到最大攻击的情况
 75                     per(j,0){  76                         
 77                         int tmp_w = 0;  78                         if (arr[i].is_s){  79                             is_s = true;  80                             tmp_w = max(0,arr[i].w - k);  81  }  82                         //对于k张魔法卡，被作用卡卡费用减少k
 83                         if (is_s && tmp_w <= j){  84                             dp[j][k] = max(dp[j][k],dp[j - tmp_w][k] + arr[i].x);  85  }  86                         else if (!is_s && arr[i].w <= j){  87                             dp[j][k] = max(dp[j][k],dp[j - arr[i].w][k] + arr[i].x);  88  }  89  }  90  }  91  }  92 
 93             is_s = false;  94  }  95 
 96         int ans = 0;  97 
 98         rep(i,m_num) ans = max(ans,dp[W][i]);//遍历费用是W的dp最大值，及为最大攻击力
 99 
100         cout << ans << endl; 101  } 102 
103 
104     return 0; 105 }