首页 > 代码库 > 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 乌龟棋
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。