NOIP2015普及组 T4 推销员

20pts

利用递归枚举组合，依次枚举C(n, m)

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int s[N], a[N], n;

int dfs(int u, int have, int m, int farest, int value){
    if (have > m || have + (n - u + 1) < m) return 0;
    if (have == m){
        return farest * 2 + value;
    }

    if (u == n + 1) return 0;
    int ret = 0;
    ret = max(ret, dfs(u + 1, have, m, farest, value));
    ret = max(ret, dfs(u + 1, have + 1, m, max(farest, s[u]), value + a[u]));

    return ret;
}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // C[n, m]
    for (int i = 1; i <= n; i++)
        cout << dfs(1, 0, i, 0, 0) << '\n';

    return 0;
}

40pts

利用区间dp， �(�3)

此时，开数组小心爆空间，从40->0，顶多能实现1e3的数据范围

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

int s[N], a[N], n;
int dp[N][N];
int ret[N];

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    dp[0][0] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            dp[i][j] = dp[i - 1][j];

            for (int k = 0; k < i; k++)
                dp[i][j] = max(dp[i][j], dp[k][j - 1] - s[k] * 2 + s[i] * 2 + a[i]);
        }
    }

    /*
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            printf("%d ", dp[i][j]);
        puts("");
    }
    */

    for (int i = 1; i <= n; i++) printf("%d\n", dp[n][i]);

    return 0;
}

100pts

利用greedy，每个点，按分值从大到小排序，维护一下额外状态， �(�)

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

struct Node{
    int s;
    int a;

    bool operator< (const Node &W)const{
        return a > W.a;
    }   
}node[N];

int n, f[N], g[N];
int h[N];

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &(node[i].s));
    for (int i = 1; i <= n; i++) scanf("%d", &(node[i].a));

    sort(node + 1, node + 1 + n);

    for (int i = 1; i <= n; i++){
        f[i] = f[i - 1] + node[i].a;          //维护Ai的从大到小的前缀和
        g[i] = max(g[i - 1], node[i].s);       //维护第i个点为止，最远的距离
    }

    // 维护[n...i]的范围，一个点，维护出来 {距离*2 + Ai}
    for (int i = n; i >= 1; i--)
        h[i] = max(h[i + 1], node[i].s * 2 + node[i].a);

    for (int i = 1; i <= n; i++){
        int x = max(f[i] + g[i] * 2,        //前i个
                    f[i - 1] + h[i]);       //前i-1个，[i..n]里面再找一个更合适的,凑起来
        printf("%d\n", x);
    }

    return 0;
}