头像

史一帆

洛阳师范学院




离线:12小时前


最近来访(276)
用户头像
来只清楚
用户头像
C14H23ClN2O
用户头像
no_one
用户头像
六角星
用户头像
FYQ357
用户头像
incra
用户头像
我是好人
用户头像
洛洛
用户头像
gAg
用户头像
笨蛋1
用户头像
稳重
用户头像
天晨
用户头像
无妄_5
用户头像
Txoon
用户头像
Mhbfy
用户头像
277
用户头像
欲小宝
用户头像
AcWing2AK
用户头像
ღSupperღ
用户头像
Cold_heartless

分享 2022/7/7

史一帆
12小时前

魔法宝石

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

using namespace std;

int n, m;
int f[3010][10010];
int v[3010], w[3010];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
    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]] + v[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

Bessie 的体重问题

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

using namespace std;

int n, m;
int f[510][45010];
int w[510];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    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 << f[n][m] << endl;
    return 0;
}

干草出售

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

using namespace std;

int n, m;
int f[50010];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        for (int j = m; j >= x; j -- )
            f[j] = max(f[j], f[j - x] + x);
    }

    cout << f[m] << endl;
    return 0;
}


分享 2022/7/6

Corn Fields

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

using namespace std;

const int N = 13, M = 1 << N, mo = 100000000;

int n, m;
int f[N][M];
int st[N];

bool check(int i, int j){
    if ((st[i] & j) != j) return false;
    if (j & (j << 1)) return false;
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ){
        st[i] = 0;
        for (int j = 1; j <= m; j ++ ){
            int x;
            scanf("%d", &x);
            st[i] = (st[i] << 1) + x;
        }
    }
    memset(f, 0, sizeof f); 
    f[0][0] = 1;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 0; j < 1 << m; j ++ ){
            if (!check(i, j)) continue;
            for (int k = 0; k < 1 << m; k ++ )
                if (!(j & k))
                    f[i][j] = (f[i][j] % mo + f[i - 1][k] % mo) % mo;
        }
    }
    int ans = 0;
    for (int i = 0; i < 1 << m; i ++ )
        ans = (ans % mo + f[n][i] % mo) % mo;
    printf("%d\n", ans);
    return 0;
}

单词接龙

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

using namespace std;

const int N = 25;

int n;
string word[N];
int used[N];
char head;
int g[N][N], ans;

void dfs(string str, int last){
    ans = max(ans, (int)str.size());
    used[last] ++ ;
    for (int i = 1; i <= n; i ++ )
        if (g[last][i] && used[i] < 2)
            dfs(str + word[i].substr(g[last][i]), i);
    used[last] -- ;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> word[i];
    cin >> head;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ){
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k ++ )
                if (a.substr(a.size() - k, k) == b.substr(0, k)){
                    g[i][j] = k;
                    break;
                }   
        }
    for (int i = 1; i <= n; i ++ )
        if (word[i][0] == head)
            dfs(word[i], i);
    cout << ans << endl;
    return 0;
}

Bugs Integrated, Inc.




分享 2022/7/5

FatMouse and Cheese

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

using namespace std;

const int N = 110;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int w[N][N], f[N][N];

int dfs(int x, int y){
    if (f[x][y] != -1) return f[x][y];
    int mx = 0;
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j < 4; j ++ ){
            int nx = x + dx[j] * i, ny = y + dy[j] * i;
            if (w[nx][ny] > w[x][y] && nx >= 1 && nx <= n && ny >= 1 && ny <= n)
                mx = max(mx, dfs(nx, ny));
        }
    return f[x][y] = mx + w[x][y];
}

int main()
{
    while (~scanf("%d%d", &n, &m)){
        if (n == -1 && m == -1) break;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                cin >> w[i][j];
        memset(f, -1, sizeof f);
        printf("%d\n", dfs(1, 1));
    }
    return 0;
}

搬寝室

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

using namespace std;

const int N = 2010;

typedef long long LL;

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

int main()
{
    while (~scanf("%d%d", &n, &m)){
        for (int i = 1; i <= n; i ++ ) cin >> w[i];
        sort(w + 1, w + 1 + n);
        memset(f, 0x3f, sizeof f);
        for (int i = 0; i <= n; i ++ ) f[i][0] = 0;
        for (int i = 2; i <= n; i ++ )
            for (int j = 1; 2 * j <= i; j ++ )
                f[i][j] = min(f[i - 1][j], f[i - 2][j - 1] + (w[i] - w[i - 1]) * (w[i] - w[i - 1]));
        printf("%lld\n", f[n][m]);
    }
    return 0;
}

Warcraft

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

using namespace std;

const int N = 110;

int n, t, q;
int v[N], w[N];
int f[N][N], ans;

int main()
{
    while (~scanf("%d%d%d", &n, &t, &q)){
        if (!n && !t && !q) break;
        ans = 0;
        for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
        v[0] = 0, w[0] = 1;
        memset(f, 0, sizeof f);
        int num = 100 / q;
        if (100 % q) num ++ ;
        for (int k = 1; k <= num; k ++ ){
            for (int j = 0; j <= 100; j ++ ){
                int next_j = min(100, j + t); 
                for (int i = 0; i <= n; i ++ ){
                    if (v[i] + j <= 100)
                        f[k][next_j] = max(f[k][next_j], f[k - 1][j + v[i]] + w[i]);
                }
                if (f[k][next_j] >= 100){
                    ans = k;
                    break;
                }
            }
            if (ans) break;
        }
        if (!ans) puts("My god");
        else printf("%d\n", ans);
    }
    return 0;
}


分享 2022/7/2

踩方格

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

using namespace std;

const int N = 25;

int n;
int s[N], w[N], e[N];

int main()
{
    s[1] = w[1] = e[1] = 1;
    cin >> n;
    for (int i = 2; i <= n; i ++ ){
        s[i] = s[i - 1] + w[i - 1] + e[i - 1];
        w[i] = s[i - 1] + w[i - 1];
        e[i] = s[i - 1] + e[i - 1];
    }
    cout << s[n] + w[n] + e[n] << endl;
    return 0;
}

盒子与球

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

using namespace std;

const int N = 15;

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

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

魔法少女

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

using namespace std;

const int N = 10010;

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

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    f[1][1] = w[1], f[2][1] = w[2];

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


分享 2022/7/4

红牌

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

using namespace std;

const int N = 2010;

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

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

数的计算

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

using namespace std;

const int N = 1010;

int n;
int f[N];

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

相似基因

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

using namespace std;

const int N = 110;

int n, m;
char s1[N], s2[N];
int p1[N], p2[N];
int f[N][N];
int g[6][6] = {
    {0},
    {0, 5, -1, -2, -1, -3},
    {0, -1, 5, -3, -2, -4},
    {0, -2, -3, 5, -2, -2},
    {0, -1, -2, -2, 5, -1},
    {0, -3, -4, -2, -1, 0}
};

int main()
{
    cin >> n >> s1 + 1 >> m >> s2 + 1;
    for (int i = 1; i <= n; i ++ ){
        if (s1[i] == 'A') p1[i] = 1;
        if (s1[i] == 'C') p1[i] = 2;
        if (s1[i] == 'G') p1[i] = 3;
        if (s1[i] == 'T') p1[i] = 4;
    }
    for (int i = 1; i <= m; i ++ ){
        if (s2[i] == 'A') p2[i] = 1;
        if (s2[i] == 'C') p2[i] = 2;
        if (s2[i] == 'G') p2[i] = 3;
        if (s2[i] == 'T') p2[i] = 4;
    }
    for (int i = 1; i <= n; i ++ )
        f[i][0] = f[i - 1][0] + g[p1[i]][5];
    for (int i = 1; i <= m; i ++ )
        f[0][i] = f[0][i - 1] + g[5][p2[i]];
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            f[i][j] = max(f[i - 1][j - 1] + g[p1[i]][p2[j]], max(f[i - 1][j] + g[p1[i]][5], f[i][j - 1] + g[5][p2[j]]));
    cout << f[n][m] << endl;    
    return 0;
}


分享 2022/7/1

超级楼梯

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

using namespace std;

const int N = 50;

typedef long long LL;

LL f[N];

int main(){
    f[1] = 0;
    f[2] = 1;
    f[3] = 2;
    for (int i = 4; i <= 40; i ++ )
        f[i] = f[i - 1] + f[i - 2];
    int T;
    cin >> T;
    while (T -- ){
        int x;
        cin >> x;
        cout << f[x] << endl;
    }
    return 0;
}

路径计数2

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

using namespace std;

const int N = 1010, mo = 100003;

typedef long long LL;

int f[N][N];
bool st[N][N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        st[a][b] = true;
    }
    f[1][1] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ){
            if (!st[i - 1][j])  f[i][j] = (f[i][j] + f[i - 1][j] % mo) % mo;
            if (!st[i][j - 1])  f[i][j] = (f[i][j] + f[i][j - 1] % mo) % mo;
        }
    cout << f[n][n] % mo << endl;

    return 0;
}

AGTC

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

using namespace std;

const int N = 1010;

typedef long long LL;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
    while (cin >> n >> a + 1 >> m >> b + 1){
        for (int i = 1; i <= n; i ++ ) f[i][0] = i;
        for (int i = 1; i <= m; i ++ ) f[0][i] = i;
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ){
                if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
                else f[i][j] = min(f[i - 1][j - 1] + 1, min(f[i - 1][j] + 1, f[i][j - 1] + 1));
            }
        cout << f[n][m] << endl;
    }

    return 0;
}


分享 2022/6/30

Common Subsequence

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

using namespace std;

const int N = 1010;

typedef long long LL;

char s1[N], s2[N];
int f[N][N];

int main(){
    while (~scanf("%s%s", s1 + 1, s2 + 1)){
        int len1 =  strlen(s1 + 1), len2 = strlen(s2 + 1);
        for (int i = 1; i <= len1; i ++ ) f[i][0] = 0;
        for (int i = 1; i <= len2; i ++ ) f[0][i] = 0;
        for (int i = 1; i <= len1; i ++ )
            for (int j = 1; j <= len2; j ++ ){
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (s1[i] == s2[j])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }
        cout << f[len1][len2] << endl;
    } 

    return 0;
}

最长公共子序列Lcs

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

using namespace std;

const int N = 1010;

typedef long long LL;

char s1[N], s2[N];
int f[N][N];
char path[N];
int pos = N-1;

int main(){
    scanf("%s%s", s1 + 1, s2 + 1);
    int len1 =  strlen(s1 + 1), len2 = strlen(s2 + 1);
    for (int i = 1; i <= len1; i ++ ) f[i][0] = 0;
    for (int i = 1; i <= len2; i ++ ) f[0][i] = 0;
    for (int i = 1; i <= len1; i ++ )
        for (int j = 1; j <= len2; j ++ ){

            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (s1[i] == s2[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    while (len1 > 0 && len2 > 0)
    {
        if (s1[len1] == s2[len2]){
            path[pos --] = s1[len1];
            len1 -- , len2 -- ;
        }else if(f[len1 - 1][len2] > f[len1][len2 - 1]) len1 -- ;
        else len2 -- ;
    }
    printf("%s\n", path + pos + 1);
    return 0;
}

Advanced Fruits

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

using namespace std;

const int N = 1010;

typedef long long LL;

char s1[N], s2[N];
int f[N][N], pre[N][N];

void print(int u, int v) {
    if (!u && !v) return;
    if (!pre[u][v]) {
        print(u - 1, v - 1);
        printf("%c", s1[u]);
    } else if (pre[u][v] == 1) {
        print(u - 1, v);
        printf("%c", s1[u]);
    } else {
        print(u, v - 1);
        printf("%c", s2[v]);
    }
}

int main() {
    while (~scanf("%s%s", s1 + 1, s2 + 1)) {

        int len1 =  strlen(s1 + 1), len2 = strlen(s2 + 1);

        for (int i = 1; i <= len1; i ++ ) f[i][0] = 0, pre[i][0] = 1;
        for (int i = 1; i <= len2; i ++ ) f[0][i] = 0, pre[0][i] = -1;
        for (int i = 1; i <= len1; i ++ )
            for (int j = 1; j <= len2; j ++ ) {
                if (s1[i] == s2[j]) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    pre[i][j] = 0;
                } else if (f[i - 1][j] > f[i][j - 1]) {
                    f[i][j] = f[i - 1][j];
                    pre[i][j] = 1;
                } else {
                    f[i][j] = f[i][j - 1];
                    pre[i][j] = -1;
                }
            }
        print(len1, len2);
        puts("");
    }

    return 0;
}


分享 2022/6/29

Super Jumping! Jumping! Jumping!

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

using namespace std;

const int N = 1010;

typedef long long LL;

int n;
int a[N];
LL f[N];

int main(){
    while (scanf("%d", &n) && n){
        memset(a, 0, sizeof a);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int i = 1; i <= n; i ++ ){
            f[i] = a[i];
            for (int j = 1; j < i; j ++ )
                if (a[j] < a[i])
                    f[i] = max(f[i], f[j] + a[i]);
        }
        LL res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
        printf("%lld\n", res);
    }
    return 0;
}

最少拦截系统

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

using namespace std;

const int N = 2010;

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

int main(){
    while (~scanf("%d", &n)){
        memset(a, 0, sizeof a);
        memset(f, 0, sizeof f);
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        for (int i = 1; i <= n; i ++ ){
            f[i] = 1;
            for (int j = 1; j < i; j ++ )
                if (a[j] < a[i])
                    f[i] = max(f[i], f[j] + 1);
        }
        int res = 0;
        for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
        printf("%d\n", res);
    }
    return 0;
}

Monkey and Banana

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

using namespace std;

const int N = 110;

int n, casei;
int f[N];
struct node{
    int l,w,h;
}p[N];

bool cmp(node A, node B){
    if (A.l != B.l) return A.l > B.l;
    else{
        if (A.w != B.w) return A.w > B.w;
        else return A.h > B.h;
    }
}

int main(){
    while (scanf("%d", &n) && n){
        memset(p, 0, sizeof p);
        memset(f, 0, sizeof f);
        int m = 0;
        for (int i = 1; i <= n; i ++ ){
            int a[3];
            scanf("%d%d%d", &a[0], &a[1], &a[2]);
            sort(a, a + 3);
            p[++ m] = {a[2],a[1],a[0]};
            p[++ m] = {a[2],a[0],a[1]};
            p[++ m] = {a[1],a[0],a[2]};
        }
        sort(p + 1, p + 1 + m, cmp);
        for (int i = 1; i <= m; i ++ ){
            f[i] = p[i].h;
            for (int j = 1; j < i; j ++ )
                if (p[j].l > p[i].l && p[j].w > p[i].w)
                    f[i] = max(f[i], f[j] + p[i].h);
        }
        int res = 0;
        for (int i = 1; i <= m; i ++ )
            res = max(res, f[i]);
        printf("Case %d: maximum height = %d\n", ++ casei, res);
    }
    return 0;
}


分享 2022/6/28

饭卡

#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;
}


分享 2022/6/27

史一帆
10天前

搬书

#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;
}