自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 21:54:28，当前版本为作者最后更新于2024-09-12 16:47:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

今天刷状压 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}$ 内。