乌龟棋
题解:动态规划
用dp[i][j][k][l]来表示第i+j* 2+k *3+l *4+1的格子可以取得的最大值
它可以由前i-1||(j-1) * 2||(k-1) * 3||(l-1) * 4的格子而来
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+10; int a[maxn],cnt[maxn]; int dp[45][45][45][45]; void solve() { int n,m,x; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=m;i++) { cin>>x; cnt[x]++; } dp[0][0][0][0]=a[1]; for(int i=0;i<=cnt[1];i++) { for(int j=0;j<=cnt[2];j++) { for(int k=0;k<=cnt[3];k++) { for(int l=0;l<=cnt[4];l++) { int ans=a[i+j*2+k*3+l*4+1]; if(i) dp[i][j][k][l]=max(dp[i-1][j][k][l]+ans,dp[i][j][k][l]); if(j) dp[i][j][k][l]=max(dp[i][j-1][k][l]+ans,dp[i][j][k][l]); if(k) dp[i][j][k][l]=max(dp[i][j][k-1][l]+ans,dp[i][j][k][l]); if(l) dp[i][j][k][l]=max(dp[i][j][k][l-1]+ans,dp[i][j][k][l]); } } } } cout<<dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]<<endl; } int main() { solve(); return 0; }