aoj2221:KULASIS
解法
16個あるボタンそれぞれについて何回押すか(0~3回)を試すと、状態がくらいあって死ぬ。
そこで、DPする。
ボタンの押し方を左上から順番に決めていく。
あるボタンを見てるときに、ボタンを押すことによる戦闘力の変化や、今後の状態遷移などのために直前7マスの情報が必要。逆に、それ以外はいらない。
よって、dp[i][j][S]:i行目でj列目のボタンをこれから押そうとしていて、なおかつ直前7マスの情報がSだったときの最大の戦闘力
という感じでdpする。
直前7マスの情報Sをどう表現するかだが、それぞれのマスの状態が5種類あって2の乗数ではないので、int型の2進数表現を利用するやり方は今回はやりずらいと思った。
そこで、直前7マスの情報を素直に配列に格納する構造体を作って、その構造体を添え字とするmapを使ってDPした。
mapの使用や、配列のコピーなどで重くなると思ったが、そこまで重くはなかった。(0.26secぐらい)
追記
他人のコードなどを読んでいると、マスの状態のうち、0の状態と1の状態を同じとみなす(ただし、0の状態の場合は状態遷移しない)と、マスの状態が4種類となって2進数表現で表しやすくなるっぽいです。すると、わざわざmapに突っ込んでめんどくさいことしなくても簡単にdpやメモ化再帰できます。(kyuridenamidaさんのaojのコードを参考にさせていただきました。ありがとうございます。)
コード
#include<bits/stdc++.h> using namespace std; struct NODE{ int m[7]; bool operator<(const NODE &n)const{ for(int i=0;i<7;i++)if(m[i]!=n.m[i])return m[i]<n.m[i]; return false; } }; int to[]={0,2,3,4,1}; int table[]={0,60,10,10,-80}; int score[]={0,0,60,70,80}; int fld[5][5]; void solve(){ for(int i=0;i<5;i++) for(int j=0;j<5;j++) cin>>fld[i][j]; map<NODE,int>prev; NODE start; for(int i=0;i<5;i++)start.m[6-i]=fld[0][i]; for(int i=0;i<2;i++)start.m[1-i]=fld[1][i]; int sum=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++) sum+=score[fld[i][j]]; prev[start]=sum; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ map<NODE,int>next; for(map<NODE,int>::iterator it=prev.begin();it!=prev.end();it++){ NODE d=it->first; int val=it->second; for(int k=0;k<4;k++){ for(int l=0;l<7;l++)if(l<2||l>=5){ val+=table[d.m[l]]; d.m[l]=to[d.m[l]]; } NODE e=d; if(j!=3){ for(int l=6;l>0;l--)e.m[l]=e.m[l-1]; e.m[0]=fld[i+1][j+2]; } else{ for(int l=6;l>1;l--)e.m[l]=e.m[l-2]; e.m[1]=fld[i+2][0]; e.m[0]=fld[i+2][1]; } if(next.find(e)!=next.end())next[e]=max(next[e],val); else next[e]=val; } } prev=next; } } int ans=0; for(map<NODE,int>::iterator it=prev.begin();it!=prev.end();it++){ ans=max(ans,it->second); } cout<<ans<<endl; } int main(){ int n; cin>>n; while(n--)solve(); return 0; }
dpのコード
#include<bits/stdc++.h> using namespace std; int dp[40][1<<14]; int v[40]; int pnt(int c){ return c>0?50+c*10:0; } int toBit(int c[7],int p){ int bit=0; for(int i=1;i<7;i++){ bit=(bit<<2)|c[i]; } bit=(bit<<2)|(~v[p+7]?v[p+7]:0); return bit; } void solve(){ memset(v,-1,sizeof(v)); for(int i=0;i<25;i++)cin>>v[i],v[i]--; memset(dp,-1,sizeof(dp)); int start=0; for(int i=0;i<7;i++)start=(start<<2)|(~v[i]?v[i]:0); dp[0][start]=0; for(int i=0;i<25;i++){ for(int S=0;S<(1<<14);S++){ if(dp[i][S]==-1)continue; int c[7]; for(int j=0;j<7;j++)c[6-j]=S>>(j*2)&3; if(i%5==4||i>=20){ dp[i+1][toBit(c,i)]=max(dp[i+1][toBit(c,i)],dp[i][S]+pnt(c[0])); continue; } for(int j=0;j<4;j++){ dp[i+1][toBit(c,i)]=max(dp[i+1][toBit(c,i)],dp[i][S]+pnt(c[0])); for(int k=0;k<7;k++)if(k<2||k>=5){ if(~v[i+k])c[k]=(c[k]+1)%4; } } } } int ans=0; for(int i=0;i<(1<<14);i++)ans=max(ans,dp[25][i]); cout<<ans<<endl; } int main(){ int n;cin>>n; while(n--)solve(); return 0; }