看題

這顯然是一道線性的dp

如何設計狀態呢？

看看題目，總共只有4張牌，而且每張牌的個數不超過40

于是狀態就很好設計了

方程如下

　　dp[i][j][k][l]=max(dp[i-1][j][k][l]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);

　　dp[i][j][k][l]=max(dp[i][j-1][k][l]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);

　　dp[i][j][k][l]=max(dp[i][j][k-1][l]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);

　　dp[i][j][k][l]=max(dp[i][j][k][l-1]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);

第一維表示用了i張1，第二維表示用了j張2，以此類推

其實是可以壓維的，因為有一種牌的數量可以由其他的牌數推出

但是我沒有寫，因為這題已經夠了

代碼很簡單易懂

#include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int N=50; int n,m,dp[N][N][N][N],c[5],sum,x,d[1000]; int main() {scanf("%d %d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&d[i]);for(int i=1;i<=m;i++){scanf("%d",&x);c[x]++;sum++;}dp[0][0][0][0]=d[0];for(int i=0;i<=c[1];i++)for(int j=0;j<=c[2];j++)for(int k=0;k<=c[3];k++){for(int l=0;l<=c[4];l++){if(i>=1)dp[i][j][k][l]=max(dp[i-1][j][k][l]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);if(j>=1)dp[i][j][k][l]=max(dp[i][j-1][k][l]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);if(k>=1)dp[i][j][k][l]=max(dp[i][j][k-1][l]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]);if(l>=1)dp[i][j][k][l]=max(dp[i][j][k][l-1]+d[i*1+j*2+k*3+l*4],dp[i][j][k][l]); }}printf("%d\n",dp[c[1]][c[2]][c[3]][c[4]]);return 0; }

?

轉載于:https://www.cnblogs.com/wzrdl/p/9781831.html

總結

以上是生活随笔為你收集整理的洛谷 1541 乌龟棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。