DP练习-初阶题（洛谷）

忘是亡心i 2023-06-30 02:51 144阅读 0赞

# DP练习-初阶题（洛谷） #

## 前言： ##

DP对我来说，一直都是比较令我头大的，现在的水平都是处于入门级的水平，这一周基本上主要就是强化DP

虽然关于DP的博客写过一点题解，但是那时候都是处于半懵的状态，但是我觉得有篇DP入门的博客还是很好的，还是打算给贴出来

链接：

[DP入门题总结 ][DP_]

个人觉得这篇博客还是可以的，就是几道经典的DP题目

第二个链接是：100个动规方程

[100个动规方程][100]

这是转载的大佬的，DP的题数不胜数，肯定是做不完的，主要是想通过做题找到寻找状态转移方程的策略和灵感

废话不多说，先复习复习这两天做的题目吧。。。。

## 题目汇总 ##

--------------------

### **第一类：背包初阶版：** ###

--------------------

说到背包，**背包9讲**是肯定要提的  
这里给出链接：

[背包九讲][Link 1]

背包九讲，觉得真的讲的很详细了，虽然后面几讲看的还是有点小迷。。。但是基本上背包问题，都可以直接或间接的转化为**0-1背包问题**

还是要做题：

--------------------

## [一、洛谷 P1060：开心的金明][P1060] ##

--------------------

**题意：**  
n块钱，m个物品，每个物品都有对应的价格w\[i\]和还有重要度v\[i\]。要求最终能够得到**价格和重要度的乘积之和最大**

**题解：**  
看上去很像0-1背包，但是又感觉和0-1背包有那么一丢丢的区别，**0-1背包问题是求最终获得的价值总和最大**，于是仔细一想，为什么不把价格和重要度相乘v\[i\]=v\[i\]\*w\[i\]，这样就和0-1背包问题等价了啊  
这道题就迎刃而解了

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #include<queue>
    #include<map>
    #include<list>
    #define INF 0x3f3f3f3f
    #define ll long long
    #define pi acos(-1.0)
    using namespace std;
    const int maxn=100;
    int v[maxn+10];
    int w[maxn+10];
    int n,m;
    int dp[30010];
    //0-1背包的简单变形题
    int main(){
        
        int x;
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;i++){
        
            scanf("%d%d",&w[i],&v[i]);
            v[i]*=w[i];               //关键所在
        }
        memset(dp,0,sizeof(dp));
        //使用滚动数组的0-1背包经典代码
        for(int i=1;i<=n;i++){
        
            for(int j=m;j>=0;j--){
        
                if(j>=w[i])
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        printf("%d\n",dp[m]);
        return 0;
    }

--------------------

## [二、洛谷 P1164:小A点菜][P1164_A] ##

--------------------

**题意：**  
M元钱，n种菜（每个菜的数量只有一份），每种菜都有对应的价格w\[i\]，求：刚好把钱花完的条件下，最多有多少种点菜方式

**题解 ：**  
其实如果要说，也是一道0-1背包的变形题，动规方程怎么找呢，开始真的很迷，看了题解才有种恍然大悟的感觉  
**状态转移方程：**  
定义**dp\[i\]\[j\]为用前i道菜用光j元钱的办法总数**，其状态转移方程如下：  
（1）if(j==第i道菜的价格)dp\[i\]\[j\]=dp\[i-1\]\[j\]+1;

（2）if(j>第i道菜的价格) dp\[i\]\[j\]=dp\[i-1\]\[j\]+dp\[i-1\]\[j-第i道菜的价格\];

（3）if(j<第i道菜的价格) dp\[i\]\[j\]=dp\[i-1\]\[j\];

于是AC代码如下：

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #include<queue>
    #include<map>
    #include<list>
    #define INF 0x3f3f3f3f
    #define ll long long
    #define pi acos(-1.0)
    using namespace std;
    const int maxn=100;
    int v[maxn+10];
    int w[maxn+10];
    int n,m;
    int dp[maxn+10][maxn+10];
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&w[i]);
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
        
            for(int j=m;j>=0;j--){
        
                if(j>w[i]){
        
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]];
                }
                else if(j==w[i])
                    dp[i][j]=dp[i-1][j]+1;
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        printf("%d\n",dp[n][m]);
        return 0;
    }

--------------------

## [三、洛谷P1048：采药][P1048] ##

--------------------

**题意：**  
m株草药，n单位的时间，每株草药都有对应的价值v\[i\]和所需要耗费的时间w\[i\]

**题解：**  
就是个裸的0-1背包，不过多解释，直接贴代码：

--------------------

## [四、洛谷P1049：装箱问题][P1049] ##

--------------------

**题意：**  
箱子的容量为m，有n个物品，每个物品有一个体积w\[i\]尽量多的装入箱子中，使得箱子剩余容量最少

**题解：**  
其实也就是0-1背包的简单变形，题目求最终箱子剩余容量最少，于是换个角度不就是求装的容量最大，然后用箱子的容量减去该值即为所求。  
不妨设：v\[i\]=w\[i\]，这样就转化为了最熟悉的0-1背包问题，于是乎就解决了

--------------------

## [五、洛谷P1616：疯狂的采药][P1616] ##

--------------------

**题意：**  
就是上面的第三题P1048的变形，0-1背包问题变成了**完全背包问题**。

**题解：**  
也不多解释，就是一个完全背包的模板题

前面几道题，感觉都还是比较裸的背包问题，于是还是来了一道比较难的题

--------------------

## [六、洛谷P1064：金明的预算方案][P1064] ##

--------------------

题意：  
上面的第一题开心的金明的改编，这同样是背包九讲中比较经典的一讲：**有依赖的背包问题**  
m元钱，n个物品；每个物品除了都有对应的价格w\[i\]，和对应的重要程度v\[i\]，还有一个区分主件和附件的标志（也就是说:当没有主件时，附件时不可以买的）

题解：  
虽然背包九讲讲的很仔细，但是自己写起来还是迷迷糊糊的，还是好好看看这个它吧

[背包九讲][Link 1]

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #include<queue>
    #include<map>
    #include<list>
    #define INF 0x3f3f3f3f
    #define ll long long
    #define pi acos(-1.0)
    using namespace std;
    const int maxn=1e5;
    int f[maxn+10];
    int h[maxn+10];
    struct node{
        
        int v,p,q;
    }a[maxn];
    int n,m;
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
        
            scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
            a[i].p*=a[i].v;
        }
        for(int i=1;i<=m;i++){
        
            if(!a[i].q){
        
                for(int j=1;j<a[i].v;j++){
        
                    h[j]=0;
                }
                for(int j=a[i].v;j<=n;j++){
        
                    h[j]=f[j-a[i].v]+a[i].p;
                }
                for(int j=1;j<=m;j++){
        
                    if(a[j].q==i){
        
                        for(int k=n;k>=a[i].v+a[j].v;k--){
        
                            h[k]=max(h[k],h[k-a[j].v]+a[j].p);
                        }
                    }
                }
                for(int j=a[i].v;j<=n;j++){
        
                    f[j]=max(f[j],h[j]);
                }
            }
        }
        printf("%d\n",f[n]);
        return 0;
    }

--------------------

### **第二类：线性动态规划** ###

--------------------

## [一、洛谷P1020：导弹拦截][P1020] ##

--------------------

**题意：**  
之前做过一道简化版，其实就是求一个最长不上升序列长度和一个最长上升子序列

**题解：**  
看了一篇比较强的题解，用的STL的**upper\_bound**和**lower\_bound**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<stack>
    #include<queue>
    using namespace std;
    const int maxn=100000;
    int n,a[maxn+10],d1[maxn+10],d2[maxn+10];
    
    int main(){
        
        n=1;
        int t=1;
        while(cin>>a[n++]){
        
            //if(t==8)
            //    break;
            //t++;
        }
        n--;
        d1[1]=a[1],d2[1]=a[1];
        int len1=1,len2=1;
        for(int i=2;i<=n;i++){
        
            if(d1[len1]>=a[i]){
        
                d1[++len1]=a[i];
            }
            else{
        
                int p1=upper_bound(d1+1,d1+1+len1,a[i],greater<int>())-d1;
                d1[p1]=a[i];
            }
            if(d2[len2]<a[i]){
        
                d2[++len2]=a[i];
            }
            else{
        
                int p2=lower_bound(d2+1,d2+1+len2,a[i])-d2;
                d2[p2]=a[i];
            }
        }
        cout<<len1-1<<endl;
        cout<<len2;
        return 0;
    }

--------------------

## [二、洛谷P1091：合唱队形][P1091] ##

--------------------

**题意：**  
n位同学，每位同学都有对应的身高，现要求合唱队形是：成一个山形，也就是“中间”（这个中间是个相对的）高，两边低，而且要**保证严格的递增和递减**

**题解：**  
其实也就是最长上升子序列的变形，我们不妨，分别两边求最长上升子序列，然后取最优值即可。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<stack>
    #include<queue>
    using namespace std;
    const int maxn=100;
    int a[maxn+10],b[maxn+10],n;
    int dp1[maxn+10],dp2[maxn+10];
    int main() {
        
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(int i=1; i<=n; i++) {
        
            scanf("%d",&a[i]);
        }
        int t=1;
        for(int i=n; i>=1; i--) {
        
            b[t++]=a[i];
        }
        for(int i=1;i<=n;i++){
        
            for(int j=0;j<i;j++){
        
                if(a[i]>a[j]){
        
                    dp1[i]=max(dp1[i],dp1[j]+1);
                }
            }
        }
        for(int i=n;i>=1;i--){
        
            for(int j=n+1;j>i;j--){
        
                if(a[i]>a[j]){
        
                    dp2[i]=max(dp2[i],dp2[j]+1);
                }
            }
        }
        int maxnum=0;
        for(int i=1;i<=n;i++){
        
            maxnum=max(dp1[i]+dp2[i]-1,maxnum);
        }
        //cout<<maxnum1<<endl;
        //cout<<maxnum2<<endl;
        cout<<n-maxnum<<endl;
        return 0;
    }

--------------------

## [三、洛谷P1280：尼克的任务][P1280] ##

--------------------

**题意：**  
尼克的工作时间为n，然后有k个任务；每个任务都有对应的开始时间点p和持续时间段t  
如果当某个任务开始的时候尼克正在忙其他的工作，那么尼克可以不用做，求：尼克能获得的最大休息时间。

**题解：**  
好吧，没搞太懂，贴个大佬的题解…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<stack>
    #include<queue>
    #define ll long long
    using namespace std;
    const int maxn=10000;
    ll sum[maxn+10],f[maxn+10];
    struct node{
        
        ll startTime,endTime;
    };
    node z[maxn+10];
    bool cmp(node a,node b){
        
        return a.startTime>b.startTime;
    }
    int main(){
        
        ll n,k,num=1;
        scanf("%lld%lld",&n,&k);
        for(ll i=1;i<=k;i++){
        
            scanf("%lld%lld",&z[i].startTime,&z[i].endTime);
            sum[z[i].startTime]++;
        }
        sort(z+1,z+k+1,cmp);
        for(ll i=n;i>=1;i--){
        
            if(sum[i]==0){
        
                f[i]=f[i+1]+1;
            }
            else{
        
                for(ll j=1;j<=sum[i];j++){
        
                    if(f[i+z[num].endTime]>f[i]){
        
                        f[i]=f[i+z[num].endTime];
                        num++;
                    }
                }
            }
        }
        cout<<f[1]<<endl;
    }

--------------------

## [四、洛谷P1880：石子合并][P1880] ##

--------------------

**题意：**  
非常经典的一个区间dp的题，也就是n堆石子，每堆石子都有一定的数量，要求所有的石子堆合并为一堆，每两堆合并的代价为两堆石子之和，注意两堆必须要相邻。  
求：最大代价和最小代价

**题解：**  
这其实就是区间DP的模板题，稍微复杂点可能是它是个环形区间DP，但是可以将数组长度增加为两倍，然后用来处理。  
由于这个数据量不是很大，所以可以不用平行四边形来进行优化，于是代码如下：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    using namespace std;
    const int maxn=1000;
    int dp1[maxn][maxn];
    int dp2[maxn][maxn];
    int a[maxn];
    int sum[maxn];
    int main(){
        
        int n;
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
            a[i+n]=a[i];
            sum[i]=sum[i-1]+a[i];
            dp1[i][i]=0;
        }
        for(int i=n+1;i<=2*n;i++){
        
            dp1[i][i]=0;
            sum[i]=sum[i-1]+a[i];
        }
        for(int len=2;len<=n;len++){
        
            for(int i=1;i<2*n-len+1;i++){
        
                int j=i+len-1;
                dp1[i][j]=0x3f3f3f3f;
                for(int k=i;k<j;k++){
        
                    dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
                    dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
                }
            }
        }
        int ans1=0x3f3f3f3f;
        int ans2=0;
        for(int i=1;i<=n;i++){
        
            ans1=min(ans1,dp1[i][i+n-1]);
            ans2=max(ans2,dp2[i][i+n-1]);
        }
        cout<<ans1<<endl;
        cout<<ans2<<endl;
        return 0;
    }

--------------------

## [五、洛谷P1140：相似基因][P1140] ##

--------------------

**题意：**  
就是求两个字符串的最大相似程度，然后有一个相似程度对比表

**题解：**  
开始是真的很懵，这个状态转移方程真的很难找啊，直到后面实在想不出看了题解才明白。

**若在第一段基因中插入空碱基相似度更优 则在第一段插入空碱基  
若在第二段基因中插入空碱基相似度更优 则在第二段插入空碱基  
若直接配对的相似度高于以上两者 则直接插入**

于是核心代码为：

for(int i=1;i<=la;i++){
        
            for(int j=1;j<=lb;j++){
        
                dp[i][j]=max(dp[i][j],dp[i][j-1]+table[b[j]][4]);
                dp[i][j]=max(dp[i][j],dp[i-1][j]+table[a[i]][4]);
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+table[a[i]][b[j]]);
            }
        }

但是要进行下预处理，具体代码为：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn=1000;
    const int table[5][5]={
        
        {
        5,-1,-2,-1,-3},
        {
        -1,5,-3,-2,-4},
        {
        -2,-3,5,-2,-2},
        {
        -1,-2,-2,5,-1},
        {
        -3,-4,-2,-1,0}
    };
    int la,lb;
    int a[maxn],b[maxn];
    int dp[maxn][maxn];
    string sa,sb;
    int main(){
        
        cin>>la>>sa;
        cin>>lb>>sb;
        for(int i=1;i<=la;i++){
        
            for(int j=1;j<=lb;j++){
        
                dp[i][j]=-INF;
            }
        }
        for(int i=1;i<=la;i++){
        
            if(sa[i-1]=='A')
                a[i]=0;
            if(sa[i-1]=='C')
                a[i]=1;
            if(sa[i-1]=='G')
                a[i]=2;
            if(sa[i-1]=='T')
                a[i]=3;
        }
        for(int i=1;i<=lb;i++){
        
            if(sb[i-1]=='A')
                b[i]=0;
            if(sb[i-1]=='C')
                b[i]=1;
            if(sb[i-1]=='G')
                b[i]=2;
            if(sb[i-1]=='T')
                b[i]=3;
        }
        for(int i=1;i<=la;i++)
            dp[i][0]=dp[i-1][0]+table[a[i]][4];
        for(int i=1;i<=lb;i++)
            dp[0][i]=dp[0][i-1]+table[b[i]][4];
        for(int i=1;i<=la;i++){
        
            for(int j=1;j<=lb;j++){
        
                dp[i][j]=max(dp[i][j],dp[i][j-1]+table[b[j]][4]);
                dp[i][j]=max(dp[i][j],dp[i-1][j]+table[a[i]][4]);
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+table[a[i]][b[j]]);
            }
        }
        printf("%d\n",dp[la][lb]);
        return 0;
    }

--------------------

### **第三类：多维动态规划** ###

--------------------

## [一、洛谷P1508：Likecloud-吃、吃、吃][P1508_Likecloud-] ##

--------------------

**题意：**  
有一个人从最下面中间开始走，走到最上面，但是要求是走的话只能向前走（也就是正前方，左前方，右前方；不能回头），每个点都有一个对应点价值，求：最终获得的价值和最大

**题解：**  
其实这还是很容易想到dp的，  
状态转移方程为：  
**dp\[i\]\[j\]=max(max(dp\[i-1\]\[j\],dp\[i-1\]\[j-1\]),dp\[i-1\]\[j+1\])+mp\[i\]\[j\];**

于是代码为：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=1000;
    int mp[maxn][maxn];
    int dp[maxn][maxn];
    int n,m;
    int main(){
        
        memset(dp,0,sizeof(dp));
        memset(mp,-inf,sizeof(mp));
        cin>>m>>n;
        int sx,sy;
        sx=m,sy=n/2+1;
        for(int i=1;i<=m;i++){
        
            for(int j=1;j<=n;j++){
        
                scanf("%d",&mp[i][j]);
            }
        }
        for(int i=1;i<=m;i++){
        
            for(int j=1;j<=n;j++){
        
                dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+mp[i][j];
            }
        }
        printf("%d\n",max(max(dp[sx][sy],dp[sx][sy-1]),dp[sx][sy+1]));
        return 0;
    }

--------------------

## [二、洛谷P1006：传纸条][P1006] ##

--------------------

**题意：**  
n行m列矩阵，每个点都有对应的价值。从左上角走到有下角，然后再从右下角走到左上角，要求不能重复走，然后求：获得的最大价值和

**题解：**  
其实也是很容易想到DP的，但是比较复杂的是：它不能要求重复，开始还是比较容易想到思维dp的，但是后面看题解说，如果数据量稍微大一点思维，就有可能为tle  
状态转移方程为：  
**dp\[i\]\[j\]\[k\]\[l\]=max(dp\[i\]\[j-1\]\[k-1\]\[l\],dp\[i-1\]\[j\]\[k\]\[l-1\],dp\[i\]\[j-1\]\[k\]\[l-1\],dp\[i-1\]\[j\]\[k-1\]\[l\])+mp\[i\]\[j\]+mp\[k\]\[l\];**  
（其中i，j表示去，k，l表示回，要求不能重复，所有l>j）

于是完整代码为：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=55;
    int mp[maxn][maxn];
    int dp[maxn][maxn][maxn][maxn];
    int n,m;
    int max_num(int a,int b,int c,int d){
        
        if(a<b)
            a=b;
        if(a<c)
            a=c;
        if(a<d)
            a=d;
        return a;
    }
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                scanf("%d",&mp[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]=max_num(dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1],dp[i-1][j][k-1][l])+mp[i][j]+mp[k][l];
                    }
                }
            }
        }
        printf("%d\n",dp[n][m-1][n-1][m]);
        return 0;
    }

--------------------

## [三、洛谷P1387：最大正方形][P1387] ##

--------------------

**题意：**  
在一个n\*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。

**题解：**  
状态转移方程：

if(mp[i][j]==1){
        
            dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
    }

完整代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=110;
    int n,m;
    int mp[maxn][maxn];
    int dp[maxn][maxn];
    int main(){
        
        cin>>n>>m;
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                scanf("%d",&mp[i][j]);
            }
        }
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                if(mp[i][j]==1){
        
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                ans=max(ans,dp[i][j]);
            }
        }
        cout<<ans<<endl;
        return 0;
    }

--------------------

## [四、洛谷P1417：烹调方案][P1417] ##

--------------------

**题意：**  
时间为t，有n个食材；每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t\*bi的美味指数，用第i件食材做饭要花去ci的时间。  
求：获得的最大美味指数

**题解：**  
开始还是没有想到，感觉应该和背包有点关，但是这种背包又不熟，直到后面看题解后，发现DP果然要走的路实在是太长了，太考思维了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]  
看的别人的题解…

于是代码为：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const ll maxn=100010;
    ll n,m;
    struct node{
        
        ll a,b,c;
    };
    node w[maxn];
    ll dp[maxn];
    bool cmp(node x,node y){
        
        return x.c*y.b<y.c*x.b;
    }
    int main(){
        
        memset(dp,0,sizeof(dp));
        memset(w,0,sizeof(w));
        cin>>m>>n;
        for(ll i=1;i<=n;i++){
        
            scanf("%lld",&w[i].a);
        }
        for(ll i=1;i<=n;i++){
        
            scanf("%lld",&w[i].b);
        }
        for(ll i=1;i<=n;i++){
        
            scanf("%lld",&w[i].c);
        }
        //先进行排序，然后就是0-1背包处理
        sort(w+1,w+n+1,cmp);
        for(ll i=1;i<=n;i++){
        
            for(ll j=m;j>=w[i].c;j--){
        
                dp[j]=max(dp[j],dp[j-w[i].c]+w[i].a-j*w[i].b);
            }
        }
        ll ans=0;
        for(ll i=1;i<=m;i++){
        
            ans=max(ans,dp[i]);
        }
        printf("%lld\n",ans);
        return 0;
    }

--------------------

## [五、洛谷P1855：榨取kkksc03][P1855_kkksc03] ##

--------------------

**题意：**  
有n个愿望，m元钱，t单位时间。每个愿望有两个属性：所需要相对应的时间和金钱

**题解：**  
开始还没有想到，虽然知道是个背包，还是没有好好理解或者说是记住吧，因为它就是个**二维费用的背包问题**

于是状态转移方程为：  
**dp\[j\]\[k\]=max(dp\[j\]\[k\],dp\[j-w1\[i\]\]\[k-w2\[i\]\]+1);**  
(这里运用了滚动数组）

于是完整代码为：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=210;
    int n,m,t;
    int w1[maxn];
    int w2[maxn];
    int dp[maxn][maxn];            //利用了滚动数组
    int main(){
        
        cin>>n>>m>>t;
        for(int i=1;i<=n;i++){
        
            cin>>w1[i]>>w2[i];
        }
        //二维费用背包问题
        for(int i=1;i<=n;i++){
        
            for(int j=m;j>=w1[i];j--){
        
                for(int k=t;k>=w2[i];k--){
        
                    dp[j][k]=max(dp[j][k],dp[j-w1[i]][k-w2[i]]+1);
                }
            }
        }
        printf("%d\n",dp[m][t]);
        return 0;
    }

--------------------

## [六、洛谷P1736：创意吃鱼法][P1736] ##

--------------------

**题意：**  
给一个只含0 、1矩阵，然后求：一个子矩阵为正方形，而且只有对角线为1，其余都为0。求对角的最大长度

**题解：**  
不懂。。。。  
只能附一个别人的题解了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 2]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #include<cmath>
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=2510;
    int n,m;
    int mp[maxn][maxn];
    int s1[maxn][maxn];
    int s2[maxn][maxn];
    int dp[maxn][maxn];
    int main(){
        
        cin>>n>>m;
        int ans=0;
        //第一遍：左上->右下
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                scanf("%d",&mp[i][j]);
                if(mp[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;
                }
                ans=max(ans,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(mp[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;
                }
                ans=max(ans,dp[i][j]);
            }
        }
        cout<<ans<<endl;
        return 0;
    }

[DP_]: https://blog.csdn.net/boliu147258/article/details/89843491
[100]: https://blog.csdn.net/boliu147258/article/details/103973516
[Link 1]: https://www.kancloud.cn/kancloud/pack/70124
[P1060]: https://www.luogu.com.cn/problem/P1060
[P1164_A]: https://www.luogu.com.cn/problem/P1164
[P1048]: https://www.luogu.com.cn/problem/P1048
[P1049]: https://www.luogu.com.cn/problem/P1049
[P1616]: https://www.luogu.com.cn/problem/P1616
[P1064]: https://www.luogu.com.cn/problem/P1064
[P1020]: https://www.luogu.com.cn/problemnew/solution/P1020
[P1091]: https://www.luogu.com.cn/problem/P1091
[P1280]: https://www.luogu.com.cn/problem/P1280
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020011421220783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4,size_16,color_FFFFFF,t_70
[P1880]: https://www.luogu.com.cn/problem/P1880
[P1140]: https://www.luogu.com.cn/problem/P1140
[P1508_Likecloud-]: https://www.luogu.com.cn/problem/P1508
[P1006]: https://www.luogu.com.cn/problem/P1006
[P1387]: https://www.luogu.com.cn/problem/P1387
[P1417]: https://www.luogu.com.cn/problem/P1417
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200114220104817.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4,size_16,color_FFFFFF,t_70
[P1855_kkksc03]: https://www.luogu.com.cn/problem/P1855
[P1736]: https://www.luogu.com.cn/problem/P1736
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020011422212454.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4,size_16,color_FFFFFF,t_70