CodeCraft-20 (Div. 2)E（状压DP）

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 typedef struct node{
 5     int val;
 6     int w[10];
 7 }srt;
 8 srt a[100007];
 9 bool cmp(srt a,srt b){
10     return a.val>b.val;
11 }
12 long long dp[100007][130];
13 int main(){
14     ios::sync_with_stdio(false);
15     cin.tie(NULL);
16     cout.tie(NULL);
17     int n,p,kk;
18     cin>>n>>p>>kk;
19     for(int i=1;i<=n;++i)
20         cin>>a[i].val;
21     for(int i=1;i<=n;++i)
22         for(int j=1;j<=p;++j)
23             cin>>a[i].w[j-1];
24     sort(a+1,a+1+n,cmp);//按照作为啦啦队贡献从大到小排序，后面的队员只能作为参赛队员，因为啦啦队员一定在前p+kk个中产生
25     memset(dp,0xcf,sizeof(dp));//初始化为一个很小的负数，以便未处理的状态值最小
26     dp[0][0]=0;
27     for(int i=1;i<=n;++i){
28         for(int j=0;j<1<<p;++j){
29             for(int k=0;k<p;++k)
30                 if(j&(1<<k))//第i个人补第k个位置
31                     dp[i][j]=max(dp[i][j],dp[i-1][j^(1<<k)]+a[i].w[k]);//更新最大值
32             int mx=i-1;//已经有多少个啦啦队员
33             for(int k=0;k<p;++k)
34                 if(j&(1<<k))
35                     --mx;//其中有些作为参赛队员
36             if(mx<kk)//啦啦队还有空缺
37                 dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].val);//更新最大值
38             else
39                 dp[i][j]=max(dp[i][j],dp[i-1][j]);//向后推
40         }
41     }
42     cout<<dp[n][(1<<p)-1];
43     return 0;
44 }