code1068 乌龟棋

暴力显然不行，所以考虑dp

记f[i][j][k][l]为使用i张1，j张2，k张3，l张4所得到的最大分数。

对于每个f[i][j][k][l]，都可以由i-1张1，j张2，k张3，l张4所得到，

或者i张1，j-1张2，k张3，l张4所得到，

或者i张1，j张2，k-1张3，l张4所得到，

i张1，j张2，k张3，l-1张4所得到的最大分数，

四者取max。

当然，还需加上它当前位置的分数。

当前位置为a[i+j*2+k*3+l*4+1]（初始位置是1）

代码如下：

#include<iostream>

#include<cstring>

using namespace std; 

int f[][][][];

int s[];

int n,m;

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++){

        cin>>s[i];

    }

    int a,b,c,d;

    a=b=c=d=;

    int x;

    for(int i=;i<=m;i++){

        cin>>x;

        switch(x){

            case :a++;break;

            case :b++;break;

            case :c++;break;

            case :d++;break;

        }

    }

    for(int i=;i<=a;i++){

        for(int j=;j<=b;j++){

            for(int k=;k<=c;k++){

                for(int l=;l<=d;l++){

                    int& ans=f[i][j][k][l];

                    if(i>)ans=max(ans,f[i-][j][k][l]);

                    if(j>)ans=max(ans,f[i][j-][k][l]);

                    if(k>)ans=max(ans,f[i][j][k-][l]);

                    if(l>)ans=max(ans,f[i][j][k][l-]);

                    ans+=s[i+j*+k*+l*+];

                }

            }

        }

    }

    cout<<f[a][b][c][d];

    return ;

}

在编写这个程序的过程中犯了一点小错误，在循环开始前把f[0][0][0][0]=s[1]

自认为考虑非常周到，把边界写上了，其实不用

在循环i=j=k=l=0的时候4个if都不进，最后ans+=s[i+j*2+k*3+l*4+1]其实已经把s[1]的值赋值给f[0][0][0][0]了，前面再画蛇添足就是错误的。

看来边界问题是一个非常有趣（坑）的问题啊...

巴特西

code1068 乌龟棋

最新文章

热门文章