2 条题解

  • 1
    @ 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;
    }
    

    信息

    ID
    222
    时间
    1000ms
    内存
    128MiB
    难度
    2
    标签
    递交数
    73
    已通过
    47
    上传者