直接hash+爆搜即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 #include <map> 7 #define inf 0x3fffffff 8 using namespace std; 9 int n,m,a[2][15][15]; 10 map<long long,int> mm; 11 struct data{ 12 int x[12],o; 13 }dd; 14 long long geth(data d){ 15 long long ans=0; 16 for(register int i=1;i<=n;++i)ans=ans*13+d.x[i]; 17 return ans; 18 } 19 int dfs(data d){ 20 if(d.x[n]==m)return 0; 21 long long H=geth(d); 22 if(mm.count(H))return mm[H]; 23 data nd; 24 int ans=-inf; 25 for(register int i=1;i<=n;++i)if(d.x[i]<m&&(i==1||d.x[i-1]>d.x[i])){ 26 nd=d;nd.o^=1;++nd.x[i]; 27 ans=max(ans,a[d.o][i][d.x[i]+1]-dfs(nd)); 28 } 29 return mm[H]=ans; 30 } 31 int main(){ 32 scanf("%d%d",&n,&m); 33 for(register int i=1;i<=n;++i) 34 for(register int j=1;j<=m;++j) 35 scanf("%d",&a[0][i][j]); 36 for(register int i=1;i<=n;++i) 37 for(register int j=1;j<=m;++j) 38 scanf("%d",&a[1][i][j]); 39 dd.o=0; 40 memset(dd.x,0,sizeof dd.x); 41 printf("%d ",dfs(dd)); 42 return 0; 43 }