题目地址：https://www.luogu.org/problemnew/show/P1063
输入输出格式
输入格式：
第一行是一个正整数N(4≤N≤100)N(4≤N≤100)，表示项链上珠子的个数。第二行是NN个用空格隔开的正整数，所有的数均不超过10001000。第ii个数为第ii颗珠子的头标记(1≤i≤N)(1≤i≤N)，当i<Ni<N时，第ii颗珠子的尾标记应该等于第i+1i+1颗珠子的头标记。第NN颗珠子的尾标记应该等于第11颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式：
一个正整数E(E≤2.1 times (10)^9)E(E≤2.1×(10)
9
)，为一个最优聚合顺序所释放的总能量。
输入输出样例
输入样例#1：
4
2 3 5 10

输出样例#1：
710

#include <iostream>
using namespace std;
int n,e[300],s[300][300],maxn = -1,res;
int main(int argc, char** argv) {
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> e[i];
        e[i+n] = e[i];
    }
    for(int i = 2;i<2*n;i++){
        for(int j = i-1;i-j<n&&j>=1;j--){
            for(int k = j;k<i;k++){
                s[j][i] = max(s[j][i],s[j][k] + s[k+1][i] + e[j]*e[k+1]*e[i+1]);
                res = max(res,s[j][i]);
            }
        }
    }
    cout << res;
    return 0;
}

地址:https://www.luogu.org/problemnew/show/P1541

我们要想办法表示之前的状态，经过题意可得，拿牌的顺序会影响之后的得分，所以这里我们不能简单用二维背包DP来做，那我们要想办法枚举所有的状态 总共有四种牌，那么就是dpac 分别表示 a牌的数量b牌的数量c牌的数量d牌的数量

代码：

#include <iostream>
#include <cstring>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int N,M,a[355],dp[45][45][45][45],g[5];
int main(int argc, char** argv) {
    cin >> N >> M;
    for(int i = 1;i<=N;i++){
        cin >> a[i];
    }
    for(int i = 1;i<=M;i++){
        int t;
        cin >> t;
        g[t]++;
    }
    dp[0][0][0][0] = a[1];
    for(int i = 0;i<=g[1];i++){
        for(int j = 0;j<=g[2];j++){
            for(int k = 0;k<=g[3];k++){
                for(int l = 0;l<=g[4];l++){
                    int r = 1+i+j*2+k*3 + l*4;
                    if(i != 0){
                        dp[i][j][k][l] = max(dp[i][j][k][l],dp[i-1][j][k][l]+a[r]);
                    }
                    if(j != 0){
                        dp[i][j][k][l] = max(dp[i][j][k][l],dp[i][j-1][k][l]+a[r]);
                    }
                    if(k != 0){
                        dp[i][j][k][l] = max(dp[i][j][k][l],dp[i][j][k-1][l]+a[r]);
                    }
                    if(l != 0){
                        dp[i][j][k][l] = max(dp[i][j][k][l],dp[i][j][k][l-1]+a[r]);
                    }
                    
                }
            }
        }
    }
    cout << dp[g[1]][g[2]][g[3]][g[4]] << endl;
    return 0;
}

题目背景
感谢@throusea 贡献的两组数据

题目描述
回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。

在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。

猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？

输入输出格式
输入格式：
有多组输入数据，每组数据：

第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

对于30%的数据，有n,m≤100

对于60%的数据，有n,m≤1000

对于100%的数据，有n,m≤2500

输出格式：
只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。

输入输出样例
输入样例#1：
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

输出样例#1：
3

判定子矩阵里是否只有对角线才有1 需要对数据进行预处理
s1i表示i,j的左边或右边有多少个为0
s2i表示i,j的上边有多少个为0
则只需要min(s1i,s2i-1)+arri 即可
然后再取一趟则取两条对角线 取最大值即可。

#include <iostream>
#include <cstring>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int n,m,arr[2505][2505],dp[2505][2505],res,s1[2505][2505],s2[2505][2505];
int main(int argc, char** argv) {
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin >> arr[i][j];
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(arr[i][j] == 0){
                s1[i][j] = s1[i][j-1] + 1;
                s2[i][j] = s2[i-1][j] + 1;
            }else{
                dp[i][j] = min(dp[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;
                res = max(res,dp[i][j]);
            }
        }
    }
    memset(dp,0,sizeof(dp));
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
    for(int i = 1;i<=n;i++){
        for(int j = m;j>=1;j--){
            if(arr[i][j] == 0){
                s1[i][j] = s1[i][j+1] + 1;
                s2[i][j] = s2[i-1][j] + 1;
            }else{
                dp[i][j] = min(dp[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;
                res = max(res,dp[i][j]);
            }
        }
    }
    cout << res << endl;
    return 0;
}

题目背景
由于你的帮助，火星只遭受了最小的损失。但gw懒得重建家园了，就造了一艘飞船飞向遥远的earth星。不过飞船飞到一半，gw发现了一个很严重的问题：肚子饿了~

gw还是会做饭的，于是拿出了储藏的食物准备填饱肚子。gw希望能在T时间内做出最美味的食物，但是这些食物美味程度的计算方式比较奇葩，于是绝望的gw只好求助于你了。

题目描述
一共有n件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。

众所周知，gw的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大

输入输出格式
输入格式：
第一行是两个正整数T和n，表示到达地球所需时间和食材个数。

下面一行n个整数，ai

下面一行n个整数，bi

下面一行n个整数，ci

输出格式：
输出最大美味指数

输入输出样例
输入样例#1：
74 1
502
2
47

输出样例#1：
408

说明
【数据范围】

对于40%的数据1<=n<=10

对于100%的数据1<=n<=50

所有数字均小于100,000

【题目来源】

tinylic改编

解题关键:

这道题看起来是01背包，但是有需要注意的地方

对于这个我用一种易懂的方式说一下

平常做01背包的题时，由于i的价值永远是不变的，所以i讨论的顺序对结果不影响

但是这道题中，如果你先讨论了1号点，再讨论第二点，第二点的价值会减小，反之一号点会减小，这两个哪个更优是不确定的，所以如果你先讨论1号点就会错

由此，需要按优先度对所有点进行排序

#include <iostream>
#include <algorithm>
using namespace std;
long long res = 0;
long long dp[10000005];
int T,n;
struct node {
    long long a,b,c;
}a[10000005];
bool cmp(node q,node p){
    if(q.b*p.c <= q.c*p.b){
        return 0;
    }else{
        return 1;
    }
}
int main() {
    cin >> T >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i].a;
    }
    for(int i = 1;i<=n;i++){
        cin >> a[i].b;
    }
    for(int i = 1;i<=n;i++){
        cin >> a[i].c;
    }
    sort(a+1,a+1+n,cmp);
    for(int i = 1;i<=n;i++){
        for(int j = T;j>=a[i].c;j--){
            dp[j] = max(dp[j],dp[j-a[i].c] + (a[i].a - j*a[i].b));
        }
    }
    for(int i = 0;i<=T;i++){
        res = max(res,dp[i]);
    }
    cout << res;
    return 0;
}

题目描述
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个mm行nn列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1(1,1)，小轩坐在矩阵的右下角，坐标(m,n)(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用00表示），可以用一个0-1000−100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这22条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的22条路径。

输入输出格式
输入格式：
输入文件，第一行有22个用空格隔开的整数mm和nn，表示班里有mm行nn列。

接下来的mm行是一个m times nm×n的矩阵，矩阵中第ii行jj列的整数表示坐在第ii行jj列的学生的好心程度。每行的nn个整数之间用空格隔开。

输出格式：
输出文件共一行，包含一个整数，表示来回22条路上参与传递纸条的学生的好心程度之和的最大值。

输入输出样例
输入样例#1：
3 3
0 3 9
2 8 5
5 7 0

输出样例#1：
34

说明
【限制】

30%的数据满足：1 le m,n le 101≤m,n≤10
100%的数据满足：1 le m,n le 501≤m,n≤50
NOIP 2008提高组第三题
解题关键：
第一种做法是四维dp，这也是最好想的，设fik为从小渊传到小轩的纸条到达(i,j)，从小轩传给小渊的纸条到达(k,l)的路径上取得的最大的好心程度和。

完全可以换一个思路想，即求从给定的起点出发走到指定位置的两条最短严格不相交路线。

那么特别显然，转移方程是 fik=max( fik-1 , fi-1k , fik , fi-1k-1 )+ai+ak。

要小心l的枚举范围，应该是从j+1到m，只有这样，在枚举第二条路的时候可以控制下标的l不会和j有相等的可能，这样可以保证两条路一定不相交（想一想，为什么）

由于终点的值是0，所以目标状态就是fnn-1。
并且要判断是否 i==k && j == l 如果相等则要减掉一个 否则就是重复

#include <iostream>
using namespace std;
int dp[100][100][100][100],a[100][100];
int n,m;
int mmax(int a,int b,int c,int d){
    if(b > a){
        a = b;
    }
    if(c > a){
        a = c;
    }
    if(d > a){
        a= d;
    }
    return a;
}
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    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++){
            for(int k = 1;k<=n;k++){
                for(int l = j+1;l <= m;l++){
                     dp[i][j][k][l]=mmax(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])+a[i][j]+a[k][l];
                        if(i==k&&l==j)dp[i][j][k][l]-=a[i][j];
                }
            }
        }
    }
    cout << dp[n][m-1][n-1][m] << endl;
    return 0;
}

第二种方法：三维数组
思路其它题解说的很清楚了，就是看成同时从左上开始传两个纸条，用f(i,j,k)表示这一步的横纵坐标之和为i，第一张纸条纵坐标为j，第二张纸条纵坐标为k（因为路径不重合，所以j≠k，不妨令j<k）。可以看出每走一步纸条的横纵坐标之和都会加一，所以i其实就是传递的次数+2.

每个状态可以由以下4种情况转移而来：

第一张纸条由上面，第二张纸条由上面 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k-1)+aj+ak}

第一张纸条由上面，第二张纸条由左边 f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k)+aj+ak}

第一张纸条由左边，第二张纸条由上面 f(i,j,k)=max{f(i,j,k),f(i-1,j,k-1)+aj+ak}

第一张纸条由左边，第二张纸条由左边 f(i,j,k)=max{f(i,j,k),f(i-1,j,k)+aj+ak}

可以看出，每种转移都是在一定情况下才能发生的（没有越界，而且纸条没有重合）。由于一开始数组中都是0，不进行越界判断也无妨，但是纸条重合的判断必须有，即只有k-1>j时才能由第3种情况转移.

#include <iostream>
using namespace std;
int dp[200][100][100],a[100][100];
int n,m;
int mmax(int a,int b,int c,int d){
    if(b > a){
        a = b;
    }
    if(c > a){
        a = c;
    }
    if(d > a){
        a= d;
    }
    return a;
}
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin >> a[i][j];
        }
    }
    for(int k = 1; k<= n + m -1 ;k++){
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                if(k - i + 1 < 1 || k - j + 1 < 1) { //步数是否合法 
                    continue;
                }
                dp[k][i][j] = mmax(dp[k-1][i][j],dp[k-1][i-1][j-1],dp[k-1][i][j-1],dp[k-1][i-1][j]) + a[i][k-i+1] + a[j][k-j+1];
                if(i == j){
                    dp[k][i][j] -= a[i][k-i+1];
                }
            }
        }
    }
    cout << dp[n+m-1][n][n] << endl;
    return 0;
}