1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 1000000000
#define offset 8
using namespace std;
typedef long long ll;
int n,d[1005],t[1005],f[1005][257][17];
int (){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int val(int x,int y){
return (x<=0)?0:(t[x]^t[y]);
}
void solve(){
for(int i=1;i<=n+1;i++)
for(int j=0;j<(1<<8);j++)
for(int k=-8;k<=7;k++)
f[i][j][k+offset]=INF;
f[1][0][-1+offset]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<8);j++){
for(int k=-8;k<=7;k++){
if(f[i][j][k+offset]>=INF)continue;
if(j&1)
f[i+1][j>>1][k-1+offset]=min(f[i+1][j>>1][k-1+offset],f[i][j][k+offset]);
else{
int r=n+2;
for(int u=1,v=0;v<8;v++,u<<=1){
if((j&u)==0){
if(i+v>r)break;
r=min(r,i+v+d[i+v]);
f[i][j|u][v+offset]=min(f[i][j|u][v+offset],f[i][j][k+offset]+val(i+k,i+v));
}
}
}
}
}
}
}
void init(){
int T=read();
while(T--){
n=read(),d[0]=n+2;
for(int i=1;i<=n;i++)t[i]=read(),d[i]=read();
solve();
int ans=INF;
for(int i=-8;i<=-1;i++)
ans=min(ans,f[n+1][0][i+offset]);
printf("%dn",ans);
}
}
int main(){
init();
return 0;
}
|
近期评论