UVA1240 ICPC Team Strategy 做题记录
看到 \(n \le 12\)，考虑搜索。但是过不去，于是加上记忆化搜索即可。因为 \(n\) 不大，选了什么题可以状压进一个数里面。
注意如果你在搜索的时候不判是否满足时间，那么你在 dfs 函数开头判断超时应该返回 \(-1\) 及以下。
剩下的按照题意模拟即可。
点击查看代码
int n,a[4][maxn];
int ans;
int f[(1<<12)+5][305][4];
int dfs(int S,int t,int lst) {
if(t>300) return -114514;
if(f[S][t][lst]!=-1) return f[S][t][lst];
int ans=0;
For(j,1,3) {
if(j!=lst) {
For(i,1,n) {
if(!((S>>(i-1))&1))
ans=max(ans,1+dfs((S|(1<<(i-1))),t+a[j][i],j));
}
}
}
return (f[S][t][lst]=ans);
}
void work() {
ans=0;
in1(n);
For(i,1,3) For(j,1,n) in1(a[i][j]);
mem(f,-1);
cout<<dfs(0,20,0)<<'\n';
}