题解：P3947 肝活动

· · 题解

今天刷状压 DP 题，发现有道题很熟悉，点进来一看才发现之前我在这题的讨论区修 markdown，今天正好回来把这题 A 了。

数据范围明示状压 DP。

设 dp_S 为打 S 中的所有歌能获得的最高分数。转移的时候，枚举最后一个打的歌，取最后分数的最大值就可以了。另外可以用一个数组记录下打 S 中的所有歌耗费的时间，可以在 DP 的时候顺便转移，就不需要在每个状态都全部再加一遍了。

题目要求字典序最小的顺序，可以用一个字符串数组 s，在 dp_S 取最大值的时候同时对应修改 s_S，为什么用字符串呢，因为 std::string 十分方便的提供了可以比较两个字符串字典序的方法，并且题目中 n\le22 的话只需要一个 char 的大小就能记录下打的是什么歌，在记录的时候转 char 即可，最后输出的时候也能直接用，十分方便。

#include<bits/stdc++.h>
using namespace std;
int n,mn,T;
char name[25][50];
int t[25],m[25];
int dp[(1<<22)];
string s[(1<<22)];
int stime[(1<<22)];
//void print(int S){
//  for(int i=1;i<=n;i++){
//      cout<<(S&(1<<(i-1)));
//  }
//}
//void prints(int S){
//  for(int i=0;i<s[S].length();i++){
//      cout<<name[s[S][i]]<<" ";
//  }
//}
int main(){
    //ios::sync_with_stdio(0);cin.tie(0);
    //cin>>n>>mn>>T;
    scanf("%d %d %d",&n,&mn,&T);
    int ts=0;
    for(int i=1;i<=n;i++){
        //cin>>name[i]>>t[i]>>m[i];
        scanf("%s %d %d",name+i,t+i,m+i);
        ts+=t[i];
    }
    if(ts>T)printf("No Answer"),exit(0);
    int temp0=(1<<n);
    for(int S=1;S<temp0;S++){
        for(int i=1;i<=n;i++){
            if(S&(1<<(i-1))){
                int last=S^(1<<(i-1));
                if(!stime[S])stime[S]=stime[last]+t[i];
                int sum=stime[last];
                int temp=dp[last]+max(0,m[i]-(sum+t[i]));
                if(temp>dp[S]){
                    dp[S]=temp;
                    s[S]=s[last]+(char)i;
                }else if(temp==dp[S]){
                    s[S]=min(s[S],s[last]+(char)i);
                }
            }
        }
        //print(S);cout<<" "<<dp[S]<<" ";prints(S);cout<<endl;
    }
    int temp=(1<<n)-1;
    int ans=dp[temp];
    if(ans<mn)printf("No Answer"),exit(0);
    printf("%d\n",ans);
    int temp2=s[temp].length();
    for(int i=0;i<temp2;i++){
        printf("%s\n",name[s[temp][i]]);
    }
    return 0;
}

在第 16 个测试点 TLE 了好一会，卡了半天的常，最后发现只要把原代码中的 if(s[S]>s[last]+(char)i)s[S]=s[last]+(char)i; 改成 s[S]=min(s[S],s[last]+(char)i); 就能瞬间压进 900\text{ms} 内。