2019年1月

题目地址: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;
}