AcWing 280. 陪审团

思路： 假设dp[i][j][d][p]代表当前背包的状态，即前i个物品选择了j个物品当前的d值和p值
考虑物品的状态依旧是选或者不选
通过下述的状态转移方程其实容易发现[i]这个维度是无用的，不需要i来存储状态的信息，所以可以去掉一个维度
即维度为dp[j][d][p]

///只有初态dp[0][0][0]为1，这样的状态转移方程可以
///得到能到达的所有状态，只有能到达的状态的值才为1
for(int i = 1; i <= n; i ++){
    for(int j = m; j > 0; j --){
        for(int d = 400; d >= drr[i]; d --){
            for(int p = 400; p >= prr[i]; p --){
                dp[j][d][p] = dp[j - 1][d - drr[i]][p - prr[i]];
            }
        }
    }
}

按照这个想法我们可以写出对应的代码，如下

#include <bits/stdc++.h>
#define mem(x) memset(x, 0, sizeof(x))
using namespace std;
const int MAXN = 205;
int n, m;
int drr[MAXN], prr[MAXN], dp[25][405][405], lujing[25][405][405];
int main(){
    int step = 0;
    while(cin >> n >> m && (n || m)){
        mem(drr), mem(prr), mem(dp), mem(lujing);
        for(int i = 1; i <= n; i ++){
            cin >> drr[i] >> prr[i];
        }
        dp[0][0][0] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = m; j > 0; j --){
                for(int d = 404; d >= drr[i]; d --){
                    for(int p = 404; p >= prr[i]; p --){
                        if(dp[j - 1][d - drr[i]][p - prr[i]] == 1){
                            dp[j][d][p] = 1;
                            lujing[j][d][p] = i; 
                        }
                    }
                }
            }
        }
        int maxs = 0x7fffffff;
        int a, b;
        a = b = 0;
        for(int i = 1; i <= 404; i ++){
            for(int j = 1; j <= 404; j ++){
                if(dp[m][i][j] == 1){
                    if(abs(i - j) < maxs){
                        maxs = abs(i - j);
                        a = i, b = j;
                    }
                    else if(abs(i - j) == maxs && i + j > a + b){
                        a = i, b = j;
                    }
                }
            }
        }
        printf("Jury #%d\n", ++ step);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", a, b);
        vector<int>vec;
        vec.clear();
        while(1){
            if(m == 0 && a == 0 && b == 0){
                break;
            }
            vec.push_back(lujing[m][a][b]);
            int aa = a, bb = b;
            a = a - drr[lujing[m][aa][bb]];
            b = b - prr[lujing[m][aa][bb]];
            m --;
        }
        sort(vec.begin(), vec.end());
        for(int i = 0; i < vec.size(); i ++){
            printf(" %d", vec[i]);
        }
        printf("\n");
    }
    return 0;
}

提交得到对应的结果：Time Limit Exceeded   
那我们要考虑如何优化时间复杂度，只能从状态入手，对状态进行压缩才能使得复杂度降低
那么把维度进行压缩，把D与P压缩成一个维度，即abs(D-P)
(D - P) + 400 这样就可以转换成为 正数
那么权值变成对应的(D + P)的和，那么状态转移方程为
dp[j][k] = dp[j - 1][k - (drr[i] - prr[i])] + drr[i] + prr[i];
从 k = (drr[i] - prr[i]) + 400 开始遍历
状态转移方程代码表示如下：

///初态应该是dp[0][400] = 0;
///其他的全为-1
///如果对应的dp[j][k - (drr[i] - prr[i])] == -1;
///那么就不能转移
///否则大于等于0就意味可以转移
    for(int i = 1; i <= n; i ++){
        for(int j = m; j > 0; j --){
            for(int k = 0; k <= 800; k++){
                dp[j][k] = dp[j][k - (drr[i] - prr[i])] + drr[i] + prr[i];   
            }
        }
    }

附上完整的代码：

#include <bits/stdc++.h>
#define mem(x) memset(x, 0, sizeof(x))
using namespace std;
const int MAXN = 205;
int drr[MAXN], prr[MAXN], dp[25][805], lujing[25][805][500];
void Init(){
    mem(drr), mem(prr), mem(lujing);
    for(int i = 0; i < 25; i ++){
        for(int j = 0; j < 805; j ++){
            dp[i][j] = -1;
        }
    }
    dp[0][400] = 0;
}
int n, m;
int main(){
    int step = 0;
    while(~scanf("%d%d", &n, &m) && (n || m)){
        Init();
        for(int i = 1; i <= n; i ++){
            scanf("%d%d", &drr[i], &prr[i]);
        }
        for(int i = 1; i <= n; i ++){
            for(int j = m; j > 0; j --){
                ///因为drr[i] - prr[i]会存在 < 0的情况
                ///按照原来的转移方程 k = 0; k <= 400; k ++
                ///dp[0][0]选了0个dsum - rsum = 0 为 1
                ///dp[m][k - (d[i] - r[i])] + d[i] + r[i]
                ///会出现负数，导致状态转移是错误的
                ///所以加上400，使得dp[0][0]变成dp[0][400]
                ///k就变成了 k = 0; k <= 800; k ++,可得如下的状态转移
                for(int k = 0; k <= 800; k ++){
                    if(k - (drr[i] - prr[i]) >= 0 && dp[j - 1][k - (drr[i] - prr[i])] >= 0 && k - (drr[i] - prr[i]) <= 800){
                        if(dp[j - 1][k - (drr[i] - prr[i])] + drr[i] + prr[i] > dp[j][k]){
                            dp[j][k] = dp[j - 1][k - (drr[i] - prr[i])] + drr[i] + prr[i];
                            lujing[j][k][dp[j][k]] = i;
                            /*
                            采用三维进行路径的标记
                            lujing的第一维度与第二维度与背包一样
                            第三维度这是背包的价值，这样的话，就可以避免重叠状态的查找
                            比如 <2 , 3> <1 , 2> 这两个二元组占用的是同一个dp[j][k]
                            那么他们的区别就是背包的价值，所以我们可以通过一个这样的
                            三维数组来标记当前的状态是因为选了哪个物体而得到的。
                            这样只要减去选择的物体就可以得到前一个的状态，从而实现路径的输出
                             */
                        }
                    }
                }
            }
        }
        /*
        通过数学我们容易得知，
        a - b = x
        a + b = y

        可得 2 * a = x + y
             a = (x + y) / 2
             b = y - a
        可得p的总和 与 d的总和
        所以 a - b为 k
            a + b 为 dp[m][k]
         */
        int sum = 0x7fffffff;/// a - b
        int num = 0;/// a + b
        int re = 0;
        int flag = 0;
        for(int k = 0; k <= 800; k ++){
            if(k <= 400){
                int temp = 400 - k;
                if(temp < sum && dp[m][k] >= 0){
                    sum = temp;
                    num = dp[m][k];
                    re = k;
                    flag = 0;
                }
                else if(temp == sum && dp[m][k] >= num){
                    num = dp[m][k];
                    re = k;
                    flag = 0;
                }
            }
            else{
                int temp = k - 400;
                if(temp < sum && dp[m][k] >= 0){
                    sum = temp;
                    num = dp[m][k];
                    re = k;
                    flag = 1;
                }
                else if(temp == sum && dp[m][k] >= num){
                    num = dp[m][k];
                    re = k;
                    flag = 1;
                }
            }
        }
        int a, b;///因为a - b 存在正负，所以对应以下两种情况
        if(flag == 1){
            a = (sum + num) / 2;
            b = num - a;
        }
        else{
            a = (num - sum) / 2;
            b = num - a;
        }
        printf("Jury #%d\n", ++ step);
        printf("Best jury has value %d for prosecution and value %d for defence:\n", a, b);
        vector<int>vec;
        vec.clear();
        int k = re;
        int mysum = dp[m][k];
        while(lujing[m][k][mysum]){///寻找路径
        /*
        将选择的物体数量减一，将a-b的值减去对应的物体的(drr[i] - prr[i]), a+b的值减去对应物体的drr[i],prr[i]
        就可以得到上一个的状态。 
         */
            vec.push_back(lujing[m][k][mysum]);
            int temp = lujing[m][k][mysum];
            m --;
            k = k - (drr[temp] - prr[temp]);
            mysum = mysum - drr[temp] - prr[temp];
        }
        sort(vec.begin(), vec.end());
        for(int i = 0; i < vec.size(); i ++){
            printf(" %d", vec[i]);
        }
        printf("\n\n");///注意输出要一个空行
    }
    return 0;
}