らての精進日記

修行をします

aoj2221:KULASIS

解法

16個あるボタンそれぞれについて何回押すか(0~3回)を試すと、状態が{\displaystyle 4^{16}}くらいあって死ぬ。

そこで、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;
}