5248: [2018多省省队联测]一双木棋
容易写出暴力.
c++代码如下：
|
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 |
#include<bits/stdc++.h> #define rep(i,x,y) for(register int i = x; i <= y; ++ i) #define repd(i,x,y) for(register int i = x; i >= y; -- i) using namespace std; typedef long long ll; template<typename T>inline void read(T&x) { x = 0;char c;int sign = 1; do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c)); do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c)); x *= sign; } const int N = 11,inf = 1e9+7,M = 1e6+50; int n,m,a[N][N],b[N][N]; bool vis[N][N]; int dfs(int x,int y,bool k) { if(x == n && y == m) return k ? -b[x][y] : a[x][y]; int ans = k ? -inf : inf; vis[x][y] = 1; rep(i,1,n) rep(j,1,m) if(vis[i - 1][j] && vis[i][j - 1] && !vis[i][j]){ if(k) { ans = max(ans,dfs(i,j,k^1) - b[x][y]); } else ans = min(ans,dfs(i,j,k^1) + a[x][y]); } vis[x][y] = 0; return ans; } int main() { read(n); read(m); rep(i,1,n) rep(j,1,m) read(a[i][j]); rep(i,1,n) rep(j,1,m) read(b[i][j]); rep(i,0,m) vis[0][i] = 1; rep(i,0,n) vis[i][0] = 1; cout << dfs(1,1,0) << endl; return 0; } |
上述代码50分.
考虑如何优化
发现其实每一层当前能选的都是固定的.
那么考虑状压来表示出每一层的状态.
因为m最大为10，根据题意显然总变化不会超过10
用1表示向左边移动，0表示该层结束
那么可以用f[i][j]表示第一层从i开始，接下来状态为j
比如i = 5，j = 111010(2进制）
表示第一层为5 ,第二层为5，第三层为4，第五层为1，接下来的层均为1.
那么这样表示发现状态一定不会超过2^20
然后考虑转移即可。
c++代码如下：
|
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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include<bits/stdc++.h> #define rep(i,x,y) for(register int i = x; i <= y; ++ i) #define repd(i,x,y) for(register int i = x; i >= y; -- i) using namespace std; typedef long long ll; template<typename T>inline void read(T&x) { x = 0;char c;int sign = 1; do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c)); do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c)); x *= sign; } const int N = 21,inf = 0x3f3f3f3f,M = 1e6+50; int n,m,a[N][N],b[N][N],f[N][1<<N]; int solve(int x) { int p[50],len = 0; while(x) { p[++len] = x&1; x >>= 1; } repd(i,len,1) printf("%d",p[i]); puts(""); } int dfs(int x,int s,bool k) { if(f[x][s] != inf) return f[x][s]; if(x == m && !s) return f[x][s] = 0; f[x][s] = k ? inf : -inf; int p[N],y = 0,S = s,len = 1; memset(p,0,sizeof p); p[1] = x; while(S) { if(!(S&1)) p[++len] = x - y; else ++y; S >>= 1; } while(++len <= n) p[len] = x - y; if(x != m) if(!k) f[x][s] = max(dfs(x + 1,s<<1|1,k^1) + a[1][x + 1],f[x][s]); else f[x][s] = min(dfs(x + 1,s<<1|1,k^1) - b[1][x + 1],f[x][s]); rep(i,2,n) if(p[i] != p[i-1]){ y = 0; ++p[i]; repd(j,n,2) { int k = p[j - 1] - p[j]; while(k--) y = y<<1|1; y <<= 1; }y>>=1; if(!k) f[x][s] = max(dfs(x,y,k^1) + a[i][p[i]],f[x][s]); else f[x][s] = min(dfs(x,y,k^1) - b[i][p[i]],f[x][s]); --p[i]; } return f[x][s]; } int main() { memset(f,0x3f,sizeof f); read(n); read(m); rep(i,1,n) rep(j,1,m) read(a[i][j]); rep(i,1,n) rep(j,1,m) read(b[i][j]); cout << dfs(1,1,1) + a[1][1] << endl; return 0; } |