2 条题解

  • 2
    @ 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;
    }
    
    • 0
      @ 2021-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
      上传者