首页 > 代码库 > wikioi 1068 乌龟棋

wikioi 1068 乌龟棋

四维dp表示分别用了多少张卡后可以获得的最大分数

 1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <ctime> 5 #include <iostream> 6 #include <algorithm> 7 #include <set> 8 #include <vector> 9 #include <sstream>10 #include <queue>11 #include <typeinfo>12 13 typedef long long ll;14 using namespace std;15 int a[400];16 int b[5];17 int dp[50][50][50][50];18 int main()19 {20     memset(b,0,sizeof(b));21     int n,m;22     cin>>n>>m;23     for(int i=0;i<n;i++)24         cin>>a[i];25     for(int i=0;i<m;i++)26     {27         cin>>b[0];28         b[b[0]]++;29     }30     int ans;31     dp[0][0][0][0]=a[0];32     for(int i=0;i<=b[1];i++)33     {34         for(int j=0;j<=b[2];j++)35         {36             for(int k=0;k<=b[3];k++)37             {38                 for(int m=0;m<=b[4];m++)39                 {40                     ans=0;41                     if(i)ans=max(ans,dp[i-1][j][k][m]);42                     if(j)ans=max(ans,dp[i][j-1][k][m]);43                     if(k)ans=max(ans,dp[i][j][k-1][m]);44                     if(m)ans=max(ans,dp[i][j][k][m-1]);45                     dp[i][j][k][m]=ans+a[i+2*j+3*k+4*m];46                 }47             }48         }49     }50     cout<<dp[b[1]][b[2]][b[3]][b[4]]<<endl;51     return 0;52 }

 

wikioi 1068 乌龟棋