板子补充！

主定理

dp合集

/*//串珠成环，每个珠有头尾两个值，尾等于另一个的头是可以合在一起，得到值a*b*c
//现在已经头尾连接，求不同地方开始算的最大值
void solve(){
    int n,ans,a[209],f[209][209];cin>>n;
    for(int i=1;i<=n;i++)  cin >> a[i], a[i + n] = a[i];//处理环
    for(int l=1;l<=n;l++){
        for(int i=1;i+l<=2*n;i++){
            int j=i+l;
            for(int k=i+1;k<j;k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i][n+i]);
    cout<<ans;
}*/

/*//环形石子合并，输出最大和最小代价
void solve(){
    int n,a[205],mi[205][205],ma[205][205],sum[205],ansmax,ansmin,r;cin>>n;
    memset(mi,0x3f,sizeof(mi));memset(ma,0,sizeof(ma));
    for(int i=1;i<=n;i++) cin>>a[i],a[i+n]=a[i];
    for(int i=1;i<2*n;i++) sum[i]=sum[i-1]+a[i],mi[i][i]=ma[i][i]=0;
    for(int i=2;i<=n;i++){
        for(int j=1;i+j-1<2*n;j++){
            r=i+j-1;
            for(int k=j;k<r;k++){
                ma[j][r]=max(ma[j][r],ma[j][k]+ma[k+1][r]+sum[r]-sum[j-1]);
                mi[j][r]=min(mi[j][r],mi[j][k]+mi[k+1][r]+sum[r]-sum[j-1]);
            }
        }
    }
    ansmax=-1,ansmin=0x7ffffff;
    for(int i=1;i<n;i++)
        ansmin=min(ansmin,mi[i][i+n-1]),
        ansmax=max(ansmax,ma[i][i+n-1]);
    cout<<ansmin<<"\n"<<ansmax;
}*/

/*//一维石子合并最小值，合并代价为合成堆大小
void solve(){
    int n,m[509],sum[509],dp[309][309];cin >> n;//每堆式石子、前缀和、i-j的最小合成代价
    for(int i=1;i<=n;i++)cin>>m[i], sum[i]= sum[i - 1] + m[i];
    for(int l=1;l<n;l++){
        for(int i=1,j=l+1;j<=n;i++,j++){
            dp[i][j]=0x7ffffff;
            for(int k=i;k<j;k++)
                dp[i][j]=min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i - 1]);
        }
    }
    cout<<dp[1][n];
}*/

/*//n个物品，每个物品有s f两种价值，要求s+f全体和最大而且s和f分别的和均不为负数
int n,ans,s[409],f[409],dp[800009];
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i] >> f[i];
    memset(dp, -0x7f, sizeof(dp));
    dp[400000]=0;//从400000开始转移
    for(int i=1;i<=n;i++){
        if(s[i]>0)
            for(int j=800000;j>=s[i];j--)
                dp[j]=max(dp[j], dp[j - s[i]] + f[i]);//同0-1背包
        else
            for(int j=0;j<=800000+s[i];j++)
                dp[j]=max(dp[j], dp[j - s[i]] + f[i]);//负数要正着DP
    }
    for(int i=400000;i<=800000;i++)//因为不一定智商越大越好,所以要枚举一遍
        if(dp[i]>=0)//注意，只有能够恰放入（被更新过），以及情商非负时，才可以更新答案
            ans=max(ans,i+dp[i]-400000);
    printf("%d\n",ans);//输出答案，换行是个好习惯
}*/

/*//从属关系的背包问题-树形背包-要买某物必须先买另一物
//主件最多两个附件
void solve(){
    int n,m,v,p,q;cin>>n>>m;//总钱数，物品数量
    int mw[32009],mv[32009],fw[32009][3],fv[32009][3],f[32009];
    for(int i=1;i<=m;i++){
        cin>>v>>p>>q;//价格，重要度（倍数），对应的主件
        if(!q)//如果是主件-可以直接买
            mw[i]=v,mv[i]=v*p;
        else//如果是附件
            fw[q][0]++,//记录主件的附件个数（只记录在fw就行，fv那里没用
            fw[q][fw[q][0]]=v,//主件的个数是用来确定该附件应该填在第一个还是第二个格子里
            fv[q][fw[q][0]]=v*p;//（是第一个还是第二个附件）
    }
    for(int i=1;i<=m;i++){
        for(int j=n;j>=mw[i];j--){//01背包模板 每一个if的前提是背包能不能装下该物品
            //情况1：只要主件 和啥都不要比较
            f[j]=max(f[j],f[j-mw[i]]+mv[i]);
            //情况2：主件和附件1 和上面选出的较大值比较
            if(j>=mw[i]+fw[i][1]) f[j]=max(f[j],f[j-mw[i]-fw[i][1]]+mv[i]+fv[i][1]);
            //情况3：主件和附件2 和上面选出的较大值比较
            if(j>=mw[i]+fw[i][2]) f[j]=max(f[j],f[j-mw[i]-fw[i][2]]+mv[i]+fv[i][2]);
            //情况4：都要
            if(j>=mw[i]+fw[i][1]+fw[i][2]) f[j]=max(f[j],f[j-mw[i]-fw[i][1]-fw[i][2]]+mv[i]+fv[i][1]+fv[i][2]);
        }
    }
    cout<<f[n];
}*/

/*
//多重背包
void solve(){
    char s;int ts1,ts2,te1,te2,n,tt,f[10009];
    cin>>ts1>>s>>ts2>>te1>>s>>te2>>n;
    tt=(te1-ts1)*60+te2-ts2;
    for(int i=1;i<=n;i++){
        int t,c,p;cin>>t>>c>>p;//代价、价值、物品数量
        if(p==0)p=99999;
        for(int j=tt;j>=0;j--){
            for(int k=0;k<=p;k++){
                if(j-k*t<0) break;
                f[j]=max(f[j],f[j-k*t]+k*c);
            }
        }
    }
    cout<<f[tt];
}*/

/* 背包总结-都可以边读边处理
//多重背包-s次数-w价值-v代价-n物品数量-m背包容量
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=0;k<=s[i];k++){
                if(j-k*v[i]<0) break;
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i])
            }
//完全背包 -w代价-c价值-m背包总容量-n物品数量
    for(int i=1;i<=n;i++)
        for(j=w[i];j<=m;j++)
            f[j]=max(f[j],f[j-w[i]]+c[i]);
//零一背包 -w代价-c价值-m背包总容量-n物品数量
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--)
            f[j]=max(f[j],f[j-w[i]]+c[i]);
*/

/*//完美背包的解决方案数量
int n,m,a,dp[10009];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a;
        for(int j=m;j>a;j--)
            dp[j]+=dp[j-a];
        dp[a]++;
    }
    cout<<dp[m];
}*/

/*传纸条(1,1)->(m,n)->(1,1)第一轮只能右下，第二轮只能左上，每个人只能传一次，求经过值和最大
#define mmax(a,b) (a>b?a:b)
#define tmax(a,b,c,d)  (mmax(mmax(a,b),mmax(c,d)))
int n,m,dp[59][59][59],a[59][59],t1,t2;
void solve(){
    cin >> m >> n;
    for ( int i = 1; i <= m; ++i)
        for ( int j = 1; j <= n; ++j)
            cin >> a[i][j];
    for ( int k = 3; k <= m + n; ++k){
        t1 = min(k-1, m);
        for ( int i = 1; i <= t1; ++i){
            t2 = min(k-1, m);
            for ( int j = 2; j <= t2; ++j){
                dp[i][j][k] = tmax(
                        dp[i-1][j][k-1],
                        dp[i-1][j-1][k-1],
                        dp[i][j-1][k-1],
                        dp[i][j][k-1]
                ) + a[i][k-i] + a[j][k-j];
                if (i == j) dp[i][j][k] -= a[i][k-i];
            }
        }
    }
    cout << dp[m][m][m+n];
}*/

/*//输出最长公共上升子序列（数字
int a[509]={-1},b[509]={-1},n,m,ans,sp,tot;
int f[509][509], pre[509][509],st[509];
void solve(){
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;for(int i=1;i<=m;i++)cin>>b[i];
    a[0] = b[0] = -1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            if(a[i] == b[j]) { // 可以将a[i]加入
                for(int k = 0; k < j; ++k)
                    if(a[i] > b[k] && f[i][j] < f[i-1][k]+1) // 这里a[i]既为b[j]
                        f[i][j] = f[i-1][k]+1,pre[i][j] = k;
            }
            else  // 不能加入a[i]
                f[i][j] = f[i-1][j],
                pre[i][j] = pre[i-1][j];
        }
    for(int j = 1; j <= m; ++j) // 寻找 ans 及序列结尾所在的位置 sp
        if(ans < f[n][j])
            ans = f[n][j], sp = j;
    printf("%d\n", ans);
    for(; sp; sp = pre[n][sp]) // 寻找整个序列
        st[++tot] = b[sp];
    while(tot) printf("%d ", st[tot--]);
}*/

/*//分组背包
int zhong[1001],jia[1001],a[1001][1001],bb[1001];//物品的重量 价值 记录分组 背包
void solve() {
    int n,m,zu,mxzu = 0;//找一共有多少个分组
    cin>>m>>n;
    for(int i = 1;i <= n;++ i){
        cin>>zhong[i]>>jia[i]>>zu;
        a[zu][0] ++;//计数  记录该组最多能够有多少物品
        a[zu][a[zu][0]] = i;//记录下标
        mxzu = max(mxzu,zu);//比较找最大的那个
    }
    for(int i = 1;i <= mxzu;++ i)
        for(int j = m;j >= 0;j --)
            for(int k = 1;k <= a[i][0];++ k)
                if(j >= zhong[a[i][k]])//判断是否越界
                    bb[j] = max(bb[j],bb[j - zhong[a[i][k]]] + jia[a[i][k]]);//比较找最大的然后更新
    printf("%d\n",bb[m]);
}*/