搬书

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

using namespace std;

const int N = 5010;

int n;
int f[N];

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> f[i];
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j < i; j ++ )
            f[i] = min(f[i], f[j] + f[i - j]);
    cout << f[n] << endl;
    return 0;
}

文科生的悲哀

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

using namespace std;

const int N = 10010, mo = 19260817;

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

int main(){
    cin >> n;
    f[1][0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 4; j ++ )
            if (f[i][j]){
                if (!j)
                    f[i + 1][1] = (f[i + 1][1] % mo + f[i][j] % mo) % mo;
                else if (j == 1){
                    f[i + 1][0] = (f[i + 1][0] % mo + f[i][j] % mo) % mo;
                    f[i + 1][2] = (f[i + 1][2] % mo + f[i][j] % mo) % mo;
                }
                else if (j == 2){
                    f[i + 1][1] = (f[i + 1][1] % mo + f[i][j] % mo) % mo;
                    f[i + 1][3] = (f[i + 1][3] % mo + f[i][j] % mo) % mo;
                }
                else f[i + 1][2] = (f[i + 1][2] % mo + f[i][j] % mo) % mo;
            }
    int res = 0;
    for (int i = 0; i < 4; i ++ )
        res += f[n][i] % mo;
    cout << res % mo << endl;

    return 0;
}

乘积最大

线性dp

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

using namespace std;

const int N = 45;

int n, m;
int f[N][10];
int w[N][N];
char str[N];

int main(){
    cin >> n >> m;
    cin >> str + 1;
    for (int i = 1; i <= n; i ++ ) w[i][i] = str[i] - '0';
    for (int i = 1; i < n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            w[i][j] = w[i][j - 1] * 10 + w[j][j];
    for (int i = 1; i <= n; i ++ ) f[i][0] = w[1][i];
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int k = 1; k < i; k ++ )
                f[i][j] = max(f[i][j], f[k][j - 1] * w[k + 1][i]);
    cout << f[n][m] << endl;
    return 0;
}

dfs

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

using namespace std;

const int N = 10;

int n, m;
string str;
int p[N];
int res;

int get(int l, int r){
    int res = 0;
    for (int i = l; i <= r; i ++ ) res = res * 10 + (str[i] - '0');
    return res;
}

void dfs(int u, int v){
    if (u > m){
        int ans = 1;
        for (int i = 0; i <= m; i ++ ) ans *= get(p[i] + 1, p[i + 1]);
        res = max(res, ans);
        return;
    }
    for (int i = v; i < n; i ++ ){
        p[u] = i;
        dfs(u + 1, i + 1);
    }
}

int main(){
    cin >> n >> m;
    cin >> str;
    p[0] = -1, p[m + 1] = n - 1;
    dfs(1, 0);
    cout << res << endl;
    return 0;
}