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

using namespace std;

const int N = 50;
typedef long long ll;
ll n;
ll f[N][N],root[N][N];

void print(ll l,ll r){
    if(l > r) return;
    printf("%lld ", root[l][r]);
    if(l == r) return;
    print(l, root[l][r] - 1);
    print(root[l][r] + 1,r);
}
int main()
{
    scanf("%lld",&n);
    for(int i = 1;i <= n;i ++){
        scanf("%lld",&f[i][i]);
        root[i][i]=i;
    }
    for(int len = 1;len < n;len ++)
        for(int l = 1,r;r = len + l, r <= n;l ++)
        {
            f[l][r]=f[l + 1][r]+f[l][l];
            root[l][r] = l;
            for(int k = l + 1;k < r;k ++){
                if(f[l][r] < f[l][k - 1] * f[k + 1][r] + f[k][k]){
                    f[l][r]=f[l][k - 1] * f[k + 1][r] + f[k][k];
                    root[l][r]=k;
                }
            }
        }
    cout << f[1][n] <<endl;
    print(1,n);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#include<vector>

using namespace std;
const int N = 15;
int f[2 * N][N][N];
int n;
int a,b,c;
int w[N][N];
int main()
{
    cin >> n;    
    while(cin >> a >> b >> c,a||b||c)
    {
        w[a][b] += c;
    }
    for(int k = 2;k <= 2 * n;k ++)
    {
        for(int x1 = 1;x1 <= n;x1 ++)
        {
            for(int x2 = 1;x2 <= n;x2 ++)
            {

                int &t = f[k][x1][x2];
                if(k - x1 <= 0 || k - x1 > n || k - x2 <= 0 || k - x2 > n) continue;
                int v = w[x1][k - x1];
                if(x1 != x2) v += w[x2][k - x2];
                t = max(t,f[k - 1][x1 - 1][x2 - 1]);
                t = max(t,f[k - 1][x1 - 1][x2]);
                t = max(t,f[k - 1][x1][x2 - 1]);
                t = max(t,f[k - 1][x1][x2]);
                t += v;

            }
        }
    }
    cout << f[2 * n][n][n] << endl;
    return 0;
}

题目链接 背包九讲

我遇到了（除了样例剩下都过）问题。

错误的代码：

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

using namespace std;
int f[1000010],v[1000010],w[1000010],s[1000010];
struct edge{
    int v,w;
};
vector <edge> e[1010]; 
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i = 1;i <= n;i ++)
    {
        cin >> v[i] >> w[i] >> s[i];
        if(s[i] > 0){
            for(int k = 1;k <= s[i];k *= 2)
            {
                s[i] -= k;
                e[i].push_back({v[i]*k,w[i]*k});
            }
            if(s[i] > 0) e[i].push_back({v[i]*s[i],w[i]*s[i]});
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i]==-1){
            for(int j=V;j>=v[i];j--){
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
        else if(s[i]==0){
            for(int j=v[i];j<=V;j++){
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
        else{
            for(edge t : e[i])
                for(int j = V;j >= t.v;j --)
                    f[j] = max(f[j],f[j - t.v] + t.w);
        }
    }
    printf("%d\n",f[V]);
    return 0;
}

只有样例过不去。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include <queue>
#include <cmath>
#include <vector>
#include<cstring>

using namespace std;
int a[110][110];
int f[110][110];
int n;
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            cin >> a[i][j];

    memset(f,0x3f,sizeof f);
    f[1][1] = a[1][1];

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

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

using namespace std;
int f[110][110],a[110][110];
int main()
{
    int T;
    cin >> T;
    int n,m;
    while(T --)
    {
        memset(f,0,sizeof f);
        memset(a,0,sizeof a);
        cin >> n >> m;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                cin >> a[i][j];

        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                f[i][j] = max(f[i - 1][j],f[i][j - 1]) + a[i][j];

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

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;

const int N = 110;
int f[N][N],w[N],root,n,V,v[N];
int e[N << 1],ne[N << 1],h[N << 1],idx;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
void dfs(int u)
{
    for(int i = h[u];i != -1;i = ne[i])
    {
        int son = e[i];
        dfs(son);
        for(int j = V - v[u];j >= 0;j --)
            for(int k = 0;k <= j;k ++)
            {
                f[u][j] = max(f[u][j],f[u][j - k] + f[son][k]);
            }
    }
    for(int j = V;j >= v[u];j --) f[u][j] = f[u][j-v[u]] + w[u];
    for(int j = 1;j < v[u];j ++) f[u][j] = 0;
}
int main()
{
    cin >> n >> V;
    memset(h,-1,sizeof h);
    for(int i = 1;i <= n;i ++)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        if(p == -1) root = i;
        else add(p,i);
    }
    dfs(root);
    cout << f[root][V] << endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>

using namespace std;
const int N = 1e5 + 10;
int t;
int a[N];
int f[N][2];
int n;
int main()
{
    cin >> t;
    while(t --)
    {
        memset(f,0,sizeof f);
        memset(a,0,sizeof a);
        f[0][0] = 0;
        f[0][1] = -0x3f3f3f3f;
        cin >> n;
        for(int i = 1;i <= n;i ++) cin >> a[i];
        for(int i = 1;i <= n;i ++)
        {
            f[i][0] = max(f[i - 1][0],f[i - 1][1]);
            f[i][1] = f[i - 1][0] + a[i];
        }
        cout << max(f[n][0], f[n][1]) <<endl;
    }
    return 0;
}

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

using namespace std;
int n,m;
const int N = 1e6 + 10;
int q[N],a[N],sum[N];
int ans=-0x3f3f3f3f;
int hh,tt=-1;
int main()
{
    cin>>n>>m;

    for(int i = 1;i <= n;i ++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        ans=max(a[i],ans);
    }
    for(int i = 0;i <= n;i ++)
    {
        if(hh<=tt&&i-q[hh]>m) hh++;
        while(hh<=tt&&sum[q[tt]]>=sum[i]) tt--;
        q[++tt]=i;
        if(q[hh]!=q[tt])
            ans=max(ans,sum[q[tt]]-sum[q[hh]]);
    }
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>

using namespace std;
int v[5] = {0,10,20,50,100};
int f[1000010];
int n;
int main()
{
    cin >> n;
    f[0] = 1;
    for(int i = 1;i <= 4;i ++)
    {
        for(int j = v[i];j <= n;j ++)
        {
            f[j] += f[j - v[i]];
        }
    }
    cout << f[n] <<endl;
    return 0;
}

#include<iostream>
#include<cstdio>
#include <queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>

using namespace std;
const int N = 12;
const int M = 1 << N,K = 220;
long long f[N][K][M];
vector<int> state;
int n,k;
int cnt[M];
vector<int> head[M];
bool check(int state){
    for(int i = 0;i < n;i ++)
        if((state>>i&1)&&(state>>i+1&1))
    return false;

    return true;
}
int count(int state){
    int res = 0;

    for(int i = 0;i < n;i ++) res+=state>>i&1;

    return res;
}
int main()
{
    cin >> n >> k;
    for(int i = 0;i < 1 << n;i ++)
    {
        if(check(i)){
            state.push_back(i);
            cnt[i] = count(i);
        }
    }
    for(int a = 0;a < state.size();a ++)
        for(int b = 0;b < state.size();b ++)
        {
            int i = state[a],j = state[b];
            if(!(i&j)&&check(i|j))
            {
                head[a].push_back(b);
            }
        }
        f[0][0][0] = 1;
    for(int i = 1;i <= n + 1;i ++)
        for(int j = 0;j <= k;j ++)
            for(int a = 0;a < state.size();a ++)
                for(int b : head[a])
                {
                    int c = cnt[state[a]];
                    if(j >= c){
                        f[i][j][a]+=f[i-1][j-c][b];
                    }
                }
    printf("%lld",f[n + 1][k][0]);
}