烏龜棋（NOIP2010）

傳送門

這道題在當年應該是一道中高檔的題，如今，呵呵，隻能算得上簽到題了吧！

這顯然是dp。

我們弄一個數組f[i][j][k][l]，它表示當我們用i張1，j張2，k張3，l張4的卡片時，我們得到的最大分數。

怎麼想到的？

你把頁面翻到最小面，你就會看見這兩行字，沒錯，這絕對是暗示。

那這樣有什麼好處？

我們可以快速定位目前到了哪一個格子，因為我們已經知道用了哪些卡片。

而且我們知道這樣可以避免因為卡片順序帶來的錯誤。

代碼如下（轉移方程自己看）：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int score[];
int vis[];
int z;
int f[][][][];
int res;
int main(){
    res=-;
    memset(vis,,sizeof(vis));
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++){
        scanf("%d",&score[i]);
    }
    for(int i=;i<m;i++){
        scanf("%d",&z);
        vis[z]++;
    }
    memset(f,-,sizeof(f));
    f[][][][]=score[];
    for(int i=;i<=vis[];i++){
        for(int j=;j<=vis[];j++){
            for(int k=;k<=vis[];k++){
                for(int l=;l<=vis[];l++){
                    int now=i+*j+*k+*l+;
                    if(now<=n){
                        int& ans=f[i][j][k][l];
                        if(i>&&f[i-][j][k][l]>=){
                            ans=max(ans,f[i-][j][k][l]+score[now]);
                        }
                        if(j>&&f[i][j-][k][l]>=){
                            ans=max(ans,f[i][j-][k][l]+score[now]);
                        }
                        if(k>&&f[i][j][k-][l]>=){
                            ans=max(ans,f[i][j][k-][l]+score[now]);
                        }
                        if(l>&&f[i][j][k][l-]>=){
                            ans=max(ans,f[i][j][k][l-]+score[now]);
                        }
                        res=max(res,ans);
                    }

                }
            }
        }
    }
    printf("%d",res);
    return ;
}