SRM328 div2 hard
DP苦手だからメモ化再帰
#include <map> #include <string> #include <sstream> #include <vector> #include <cstring> using namespace std; typedef pair<bool,vector<string> > KEY; class ScoreDifference { public: int board[4][4]; int cache[2][(1<<16)]; int ABS(int num) { return num<0 ? -num : num; } bool calc(int s,int y,int x) { int a=(y*4+x); return s & (1<<a); } int rec(bool isPlayer,int canMove) { int &r=cache[(isPlayer) ? 1 : 0][canMove]; if(r!=(1<<28)) return r; if(canMove==(1<<16)-1) return 0; if(isPlayer) r=-(1<<28); else r=(1<<28); for(int y=0;y<4;y++) for(int x=0;x<4;x++) if(!calc(canMove,y,x)) { bool isCan=(y==0 || y==3 || x==0 || x==3); isCan=(isCan || (0<y && calc(canMove,y-1,x)) ); isCan=(isCan || (y<3 && calc(canMove,y+1,x)) ); isCan=(isCan || (0<x && calc(canMove,y,x-1)) ); isCan=(isCan || (x<3 && calc(canMove,y,x+1)) ); if(!isCan) continue; int c=canMove; c=(c | (1<<(y*4+x)) ); if(isPlayer) r=max(r,rec(false,c)+board[y][x]); else r=min(r,rec(true,c)-board[y][x]); } return r; } int maximize(vector <string> input) { for(int i=0;i<4;i++) { stringstream ss(input[i]); for(int j=0;j<4;j++) { int a; ss >> a; board[i][j]=a; printf("%3d",a); } printf("\n"); } for(int i=0;i<2;i++) for(int j=0;j<(1<<16);j++) cache[i][j]=(1<<28); printf("rec(true,0)=%d\n",rec(true,0)); printf("rec(false,0)=%d\n",rec(false,0)); int ans=0; ans=max(ans,rec(true,0)); ans=max(ans,rec(false,0)); return ans; } };