传送门~
题目大意
先分析((x or y)-(x and y)), 就是(x)和(y)中存在的1减去(x)和(y)中相同的1 那不就是(x xor y)么←_←
给定(n)个人, 确定一个排列, 使得不存在(i+b_i)在(i)之前, 并最小化(sum_{i=2}^{n}t_i xor t_{i-1}).
题目分析
(1leqslant b_ileqslant7), 数据范围一眼状压...
但是具体怎么定义状态呢?
假如说(最一般的想法)(f_{i,j})表示到第(i)个人的时候(前(i-1)个人已经打完饭), 后面(包括他)的打饭集合为(j)(0表示没打 1表示打了)..
但是推的时候要涉及到上一个人的打饭状态...
而上一个打饭的人不一定是(i-1)
所以我们还要记录一下上一个打饭的人...
定义状态(f_{i,j,k})表示前(i-1)个人都已经打完饭, (isim i+7)的打饭集合为(j), 上一个打饭的是(i+k).
很显然(k=-8sim 7). 而由于c++数组的尿性, 我们要(k+8)再存
然后就是考虑递推了.
-
初始化的话 因为要找最小值 全都赋值为(infty)...
边界条件(f_{1,0,-1}=0)显然. -
首先如果(j&1 eq 0), 说明第(i)个人已经打饭了, 后面的人就不会跑到他前面...
我们发现这个状态和 (f_{i+1,j>>1,k-1}) (第(i+1)个人打饭, 集合为去掉(i)后的状态, 最后一个打饭的人是((i+1)+(k-1))是一样的.. 可以直接转移过去. -
如果(j&1=0)呢? 说明第(i)个人还没有打饭. 那就不能转移到(f_{i+1,?,?})了.
我们就要从后面枚举一个人, 让他去打饭.
我们可以(1sim 7)枚举(l), 目标状态就是(f_{i,j|(1<<l),l})...
于是就出现了(f_{i,j|(1<<l),l}=min{f_{i,j,k}+t_{i+k} xor t_{i+l}})...
但是要注意第一道菜是不需要时间的, 所以要特判(i+k=0)的情况...
然后要注意的就是枚举的这个人不能引起别人的愤怒...
所以要维护一下能忍耐的范围...
一旦不能忍耐了, 那就直接break掉就行.. 因为后面的更不行了... -
最后从(f_{n+1,0,?})里面找个最小的作为(ans)就好了~
这样就做完了.
代码:
这种枚举变量个数多的dp用的tab缩进真是美如画..
#include <cstdio>
#include <cstring>
const int N=1002;
int f[N][260][17],t[N],b[N];
inline int gn(int a=0,char c=0){
for(;c<'0'||c>'9';c=getchar());
for(;c>47&&c<58;c=getchar())a=a*10+c-48;return a;
}
inline int min(const int &a,const int &b){return a<b?a:b;}
void work(){
memset(f,0x3f,sizeof(f)); int n=gn();
for(int i=1;i<=n;++i) t[i]=gn(),b[i]=gn();
f[1][0][7]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<256;++j)
for(int k=-8;k<8;++k)
if(f[i][j][k+8]<1e9){
if(j&1) f[i+1][j>>1][k+7]=min(f[i+1][j>>1][k+7],f[i][j][k+8]);
else{
int r=1e9;
for(int l=0;l<8;++l)
if(!(j&(1<<l))){
if(i+l>r) break;
if(i+l+b[i+l]<r) r=i+l+b[i+l];
f[i][j|(1<<l)][l+8]=min(f[i][j|(1<<l)][l+8],f[i][j][k+8]+(i+k?(t[i+k]^t[i+l]):0));
}
}
} int ans=1e9;
for(int i=-8;i<8;++i) ans=min(ans,f[n+1][0][i]); printf("%d
",ans);
}
int main(){
int T=gn();
while(T--)work();
}
注意事项
注意事项应该都说过了...
可能要提醒的就是多组数据, 每次记得清理f数组...
然后就是该有的特判都不要少..
一定时刻记得第三维要+8哦~
完结撒花~