饭卡

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int w[N];

int main(){
    while (cin >> n && n){
        for (int i = 1; i <= n; i ++ ) cin >> w[i];
        cin >> m;
        if (m < 5){
            cout << m << endl;
            continue;
        }
        sort(w + 1, w + 1 + n);
        int maxw = w[n];
        memset(f, 0, sizeof f);
        m -= 5;
        for (int i = 1; i < n; i ++ )
            for (int j = 0; j <= m; j ++ ){
                f[i][j] = f[i - 1][j];
                if (j >= w[i])
                    f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
            }
        cout << m + 5 - maxw - f[n - 1][m] << endl;
    }
    return 0;
}

数塔

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 110;

int n;
int f[N][N];

int main(){
    int T;
    cin >> T;
    while (T -- ){
        cin >> n;
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= i; j ++ )
                cin >> f[i][j];
        for (int i = n - 1; i >= 1; i -- )
            for (int j = 1; j <= i; j ++ )
                f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
        cout << f[1][1] << endl;
    }
    return 0;
}

免费馅饼

法一

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[11][N], f[11][N];

int main(){
    while (scanf("%d", &n) && n){
        memset(w, 0, sizeof w);
        memset(f, 0, sizeof f);
        int maxt = 0;
        for (int i = 1; i <= n; i ++ ){
            int x, t;
            scanf("%d%d", &x, &t);
            maxt = max(maxt, t);
            w[x][t] ++ ;
        }
        for (int i = 4; i <= 6; i ++ )
            f[i][1] = w[i][1];
        for (int j = 2; j <= maxt; j ++ )
            for (int i = 0; i <= 10; i ++ ){
                if (abs(5 - i) > j) f[i][j] = 0;
                else{
                    int x = w[i][j];
                    if (!i) f[i][j] = max(f[i][j - 1], f[i + 1][j - 1]) + x;
                    else if (i == 10) f[i][j] = max(f[i][j - 1], f[i - 1][j - 1]) + x;
                    else f[i][j] = max(f[i][j - 1], max(f[i - 1][j - 1], f[i + 1][j - 1])) + x;
                }
            }
        int ans = 0;
        for (int i = 0; i <= 10; i ++ )
            for (int j = 1; j <= maxt; j ++ )   
                ans = max(ans, f[i][j]);
        cout << ans << endl;
    }
    return 0;
}

法二

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int f[N][12];

int main(){
    while (scanf("%d", &n) && n){
        memset(f, 0, sizeof f);
        int maxt = 0;
        for (int i = 1; i <= n; i ++ ){
            int x, t;
            scanf("%d%d", &x, &t);
            maxt = max(maxt, t);
            f[t][x] ++ ;
        }
        for (int i = maxt - 1; i >= 0; i -- )
            for (int j = 0; j <= 10; j ++ ){
                int x = max(f[i + 1][j], f[i + 1][j + 1]);
                if (j > 0) x = max(x, f[i + 1][j - 1]);
                f[i][j] += x;
            } 
        printf("%d\n", f[0][5]);
    }
    return 0;
}