2 条题解
-
2Xian (XianYu) LV 5 @ 2021-10-17 11:13:32
#include <iostream> using namespace std; const int N = 1e2 + 10; int a[5000], c[N]; int dp[N][N][N][N]; int main(){ int m, n; cin >> n >> m; for(int i = 0; i < n; i++){ int x; cin >> x; a[i] = x; } for(int i = 0; i < m; i++){ int x; cin >> x; c[x]++; } 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++){ int num = i * 1 + j * 2 + k * 3 + l * 4; if(i > 0)dp[i][j][k][l] = dp[i-1][j][k][l]; if(j > 0)dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l]); if(k > 0)dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k-1][l]); if(l > 0)dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l-1]); dp[i][j][k][l] += a[num]; } cout << dp[c[1]][c[2]][c[3]][c[4]]; return 0; }
-
02021-8-8 2:24:21@
C++ :
#include <iostream> using namespace std; int n,m; int a[351]; int card[5]; int dp[41][41][41][41]; int Count(int c1,int c2,int c3,int c4) { return (c1*1+c2*2+c3*3+c4*4)+1; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<m;i++) { int temp; cin>>temp; card[temp]++; } dp[0][0][0][0] = a[1]; for(int i=0;i<=card[1];i++) for(int j=0;j<=card[2];j++) for(int k=0;k<=card[3];k++) for(int l=0;l<=card[4];l++) { if(i>0) dp[i][j][k][l] = max(dp[i][j][k][l],dp[i-1][j][k][l]+a[Count(i,j,k,l)]); if(j>0) dp[i][j][k][l] = max(dp[i][j][k][l],dp[i][j-1][k][l]+a[Count(i,j,k,l)]); if(k>0) dp[i][j][k][l] = max(dp[i][j][k][l],dp[i][j][k-1][l]+a[Count(i,j,k,l)]); if(l>0) dp[i][j][k][l] = max(dp[i][j][k][l],dp[i][j][k][l-1]+a[Count(i,j,k,l)]); } cout<<dp[card[1]][card[2]][card[3]][card[4]]<<endl; return 0; }
- 1
信息
- ID
- 222
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 2
- 标签
- 递交数
- 72
- 已通过
- 46
- 上传者