题解 | #[NOIP2010]乌龟棋#

dp的状态是消耗步数1、步数2、步数3、步数4的卡片，所能得到的数数值为： dp[i][j][t][y]就表示了步数1、步数2、步数3、步数4的所能得到的最大值。

#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
struct cmp{
	bool operator()(const int&a,const int&b) const{
		return a>b;
	}
};
int num[150];
int a[400];
int cardsum[5];
int dp[41][41][41][41];
int main(){
 	cin>> n>>m;
    for(int i =0;i<n;i++){
        cin>> a[i];
    }
    for(int i =0;i<m;i++){
        cin>> num[i];
        cardsum[num[i]]++;
    }
    dp[0][0][0][0]=a[0];//注意一开始就要计入第一项数值，从第一项开始起步
    for(int i =0;i<=cardsum[1];i++){//枚举步数为1的卡片
        for(int j =0;j<=cardsum[2];j++){//枚举步数为2的卡片
            for(int t =0;t<=cardsum[3];t++){//枚举步数为3的卡片
                for(int y =0;y<=cardsum[4];y++){//枚举步数为4的卡片
                    if(i!=0)
                    dp[i][j][t][y]=max(dp[i][j][t][y],dp[i-1][j][t][y]+a[i+2*j+3*t+4*y]);
                    if(j!=0)
                    dp[i][j][t][y]=max(dp[i][j][t][y],dp[i][j-1][t][y]+a[i+2*j+3*t+4*y]);
                    if(t!=0)
                    dp[i][j][t][y]=max(dp[i][j][t][y],dp[i][j][t-1][y]+a[i+2*j+3*t+4*y]);
                    if(y!=0)
                    dp[i][j][t][y]=max(dp[i][j][t][y],dp[i][j][t][y-1]+a[i+2*j+3*t+4*y]);
                }
            }
        }
    }
    cout<< dp[cardsum[1]][cardsum[2]][cardsum[3]][cardsum[4]];//输出结果，刚好用完卡片后得到的最大值。
    
    return 0;
}