2010-1137

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

vout自己填坑
题意：

{{{
Youmu要在神秘森林n个part中分别收集TIME和POINT以获取足够的力量抗击敌人。
有两个值PV和TV，在第i个part中，如果在某个时刻收集了一个POINT，那么总能量就会增加PV，同时TV值会增加a[i]，
如果收集一个TIME，那么总能量就会增加TV，同时PV值会增加b[i]。
part[i]中有x[i]个POINT和y[i]个TIME。PV和TV值都会一直保留，带入下一个part。
现在的问题是，如何安排part的顺序，以及每个part里面收集POINT和TIME的顺序，使得最后能得到的总能量最大。
}}}

思路：

{{{
首先，对于每个part，设如果在PV和TV在这个part中初始都为0时，在这个part中能收集到的最大的能量为gao[i]。
再设进入这个part之前的PV值和TV值分别为PV0和TV0，那么在这个part中实际能得到的最大能量为PV0 * x[i] + TV0 * y[i] + gao[i]。
而每个part进行完后，PV和TV肯定是分别增加了b[i] * y[i]和a[i] * x[i]，也就是说在只要知道在进入这个part之前，
已经完成了哪些part，连顺序都不用考虑，就可以知道PV0和TV0的值。因为n<=15，可以使用状态压缩的DP来求解。
再考虑如何算出gao[i]。
可以用dp的方法，设dp[x][y]为收集了x个POINT和y个TIME能得到的最大能量。
那么就有dp[x][y] = max(dp[x - 1][y] + b[i] * y, dp[x][y - 1] + a[i] * x). 这个时间复杂度为x[i] * y[i]。
}}}

这是asmn的代码：

{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>

#define INF 0x3f3f3f3f
#define MP make_pair
const int MAXN = 1011;

using namespace std;
typedef long long LL;
LL dp[35][35], add[20];
LL A, B, X[35], Y[35];
LL PV[1 << 15], TV[1 << 15], ans[1 << 15];
LL gao(int i){

    for (int x = 0; x <= X[i]; ++x){
        for (int y = 0; y <= Y[i]; ++y){
            dp[x][y] = 0;
            if (x > 0){
                dp[x][y] = max(dp[x][y], dp[x - 1][y] + B * y);
            } 
            if (y > 0){
                dp[x][y] = max(dp[x][y], dp[x][y - 1] + A * x);
            }
        }
    }
    return dp[X[i]][Y[i]];
}
int main(){
    int N, i, mask;
    while (scanf("%d", &N) != EOF){
        memset(PV, 0, sizeof(PV));
        memset(TV, 0, sizeof(TV));
        memset(ans, 0, sizeof(ans));
        for (i = 0; i < N; ++i){
            scanf("%lld%lld%lld%lld", &A, &B, &X[i], &Y[i]);
            add[i] = gao(i);
            //printf("%lld\n", add[i]);
            PV[1 << i] = Y[i] * B;
            TV[1 << i] = X[i] * A;
        }

        for (mask = 1; mask < (1 << N); ++mask){
            PV[mask] = PV[mask & -mask] + PV[mask & (mask - 1)];
            TV[mask] = TV[mask & -mask] + TV[mask & (mask - 1)];
            //printf("%d: %lld %lld\n", mask, PV[mask], TV[mask]);
            for (i = 0; i < N; ++i){
                if (mask & (1 << i)){
                    ans[mask] = max(ans[mask], add[i] + X[i] * PV[mask ^(1 << i)] + Y[i] * TV[mask ^(1 << i)] + ans[mask ^ (1 << i)]);
                }
            }
        }
        printf("%lld\n", ans[(1 << N) - 1]);

    }

}
}}}
[[BR]]
此题还有贪心方法，不妨设某个part中a[i] > b[i]。那么收集方法应该是先把所有的POINT收集，再把所有的TIME收集。反之亦然。证明如下：

{{{
设一个收集序列为*****TP*****，T代表收集了TIME，P代表收集了POINT，
那么通过交换相邻的T和P的，一定可以使得到能量增加。
设收集这个T之前，PV和TV分别为PV1和TV1，那么按照TP的顺序，得到的能量为TV1 + (PV1 + b[i])，
收集完这两个后，PV = PV1 + b[i], TV = TV1 + a[i]。
如果按照PT的顺序，收集完这两个后，PV = PV1 + b[i], TV = TV1 + a[i]是一样的，
但是得到的能量就是PV1 + (TV1 + a[i])，比TP更多。
因此，凡是遇到TP，就变为PT，这样一来，最优的顺序肯定是PPPPP……TTTTT。
于是有：gao[i] = max(a[i], b[i]) * x[i] * y[i];
}}}

以下是标程的代码，用的就是贪心方法：

{{{
#!cpp
#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long LL;
const int MAXN = 20 + 5;
int n;
int a[MAXN], b[MAXN], x[MAXN], y[MAXN], p[MAXN];
int dp[1 << 16];

int main() {
    while (scanf("%d", &n) != EOF) {
        assert(n >= 1 && n <= 15);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d%d", &a[i], &b[i], &x[i], &y[i]);
            p[i] = max(a[i], b[i]) * x[i] * y[i];
        }
        fill(dp, dp + (1 << n), 0);
        for (int i = 0; i < (1 << n); i++) {
            int pv = 0, tv = 0;
            for (int k = 0; k < n; k++) {
                if (i & (1 << k)) {
                    tv += a[k] * x[k];
                    pv += b[k] * y[k];
                }
            }
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) == 0) {
                    dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i] + pv * x[j] + tv * y[j] + p[j]);
                }
            }
        }
        printf("%d\n", dp[(1 << n) - 1]);
    }
    return 0;
}
}}}

vout自己填坑

题意：

Youmu要在神秘森林n个part中分别收集TIME和POINT以获取足够的力量抗击敌人。
有两个值PV和TV，在第i个part中，如果在某个时刻收集了一个POINT，那么总能量就会增加PV，同时TV值会增加a[i]，
如果收集一个TIME，那么总能量就会增加TV，同时PV值会增加b[i]。
part[i]中有x[i]个POINT和y[i]个TIME。PV和TV值都会一直保留，带入下一个part。
现在的问题是，如何安排part的顺序，以及每个part里面收集POINT和TIME的顺序，使得最后能得到的总能量最大。

思路：

首先，对于每个part，设如果在PV和TV在这个part中初始都为0时，在这个part中能收集到的最大的能量为gao[i]。
再设进入这个part之前的PV值和TV值分别为PV0和TV0，那么在这个part中实际能得到的最大能量为PV0 * x[i] + TV0 * y[i] + gao[i]。
而每个part进行完后，PV和TV肯定是分别增加了b[i] * y[i]和a[i] * x[i]，也就是说在只要知道在进入这个part之前，
已经完成了哪些part，连顺序都不用考虑，就可以知道PV0和TV0的值。因为n<=15，可以使用状态压缩的DP来求解。
再考虑如何算出gao[i]。
可以用dp的方法，设dp[x][y]为收集了x个POINT和y个TIME能得到的最大能量。
那么就有dp[x][y] = max(dp[x - 1][y] + b[i] * y, dp[x][y - 1] + a[i] * x). 这个时间复杂度为x[i] * y[i]。

这是asmn的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MP make_pair
const int MAXN = 1011;
using namespace std;
typedef long long LL;
LL dp[35][35], add[20];
LL A, B, X[35], Y[35];
LL PV[1 << 15], TV[1 << 15], ans[1 << 15];
LL gao(int i){
    for (int x = 0; x <= X[i]; ++x){
        for (int y = 0; y <= Y[i]; ++y){
            dp[x][y] = 0;
            if (x > 0){
                dp[x][y] = max(dp[x][y], dp[x - 1][y] + B * y);
            } 
            if (y > 0){
                dp[x][y] = max(dp[x][y], dp[x][y - 1] + A * x);
            }
        }
    }
    return dp[X[i]][Y[i]];
}
int main(){
    int N, i, mask;
    while (scanf("%d", &N) != EOF){
        memset(PV, 0, sizeof(PV));
        memset(TV, 0, sizeof(TV));
        memset(ans, 0, sizeof(ans));
        for (i = 0; i < N; ++i){
            scanf("%lld%lld%lld%lld", &A, &B, &X[i], &Y[i]);
            add[i] = gao(i);
            //printf("%lld\n", add[i]);
            PV[1 << i] = Y[i] * B;
            TV[1 << i] = X[i] * A;
        }
        for (mask = 1; mask < (1 << N); ++mask){
            PV[mask] = PV[mask & -mask] + PV[mask & (mask - 1)];
            TV[mask] = TV[mask & -mask] + TV[mask & (mask - 1)];
            //printf("%d: %lld %lld\n", mask, PV[mask], TV[mask]);
            for (i = 0; i < N; ++i){
                if (mask & (1 << i)){
                    ans[mask] = max(ans[mask], add[i] + X[i] * PV[mask ^(1 << i)] + Y[i] * TV[mask ^(1 << i)] + ans[mask ^ (1 << i)]);
                }
            }
        }
        printf("%lld\n", ans[(1 << N) - 1]);
    }
}

此题还有贪心方法，不妨设某个part中a[i] > b[i]。那么收集方法应该是先把所有的POINT收集，再把所有的TIME收集。反之亦然。证明如下：

设一个收集序列为*****TP*****，T代表收集了TIME，P代表收集了POINT，
那么通过交换相邻的T和P的，一定可以使得到能量增加。
设收集这个T之前，PV和TV分别为PV1和TV1，那么按照TP的顺序，得到的能量为TV1 + (PV1 + b[i])，
收集完这两个后，PV = PV1 + b[i], TV = TV1 + a[i]。
如果按照PT的顺序，收集完这两个后，PV = PV1 + b[i], TV = TV1 + a[i]是一样的，
但是得到的能量就是PV1 + (TV1 + a[i])，比TP更多。
因此，凡是遇到TP，就变为PT，这样一来，最优的顺序肯定是PPPPP……TTTTT。
于是有：gao[i] = max(a[i], b[i]) * x[i] * y[i];

以下是标程的代码，用的就是贪心方法：

#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long LL;
const int MAXN = 20 + 5;
int n;
int a[MAXN], b[MAXN], x[MAXN], y[MAXN], p[MAXN];
int dp[1 << 16];
int main() {
    while (scanf("%d", &n) != EOF) {
        assert(n >= 1 && n <= 15);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d%d", &a[i], &b[i], &x[i], &y[i]);
            p[i] = max(a[i], b[i]) * x[i] * y[i];
        }
        fill(dp, dp + (1 << n), 0);
        for (int i = 0; i < (1 << n); i++) {
            int pv = 0, tv = 0;
            for (int k = 0; k < n; k++) {
                if (i & (1 << k)) {
                    tv += a[k] * x[k];
                    pv += b[k] * y[k];
                }
            }
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) == 0) {
                    dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i] + pv * x[j] + tv * y[j] + p[j]);
                }
            }
        }
        printf("%d\n", dp[(1 << n) - 1]);
    }
    return 0;
}