有彩蛋

题意

从西北角走到东南角

只能往东走或南走

沿途最多能收取到多少花生

思路

拿这个样例

3 3
1 1 5
3 4 6
2 1 3

我们能知道$r=3,c=3$

花生地是

a[3][3]

1 1 5
3 4 6
2 1 3

我们先将$i=0 或 j=0$的地先都分别加上北面或西面的花生数目(因为这两条道没有别的选择)

再从$1$开始遍历,每个值为$a[i][j]+max(a[i-1][j],a[i][j-1])$

因为要取北面或西面的最多花生

输出东南角的花生数目

代码

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int t;
    cin>>t;//输入
    while(t--)
    {
    	int r,c;
    	int a[114][114];
    	cin>>r>>c;//输入
    	for(int i=0;i<r;i++)
    	{
    		for(int j=0;j<c;j++)
    		{
    			cin>>a[i][j];//输入
    			if(j==0 && i>0)a[i][j]+=a[i-1][j];//选择北面的
    			if(i==0 && j>0)a[i][j]+=a[i][j-1];//选择西面的
			}
		}
		for(int i=1;i<r;i++)//从1开始
		{
			for(int j=1;j<c;j++)//从1开始
			{
				a[i][j]+=max(a[i-1][j],a[i][j-1]);//取北面和西面的最大值
			}
		}
		cout<<a[r-1][c-1]<<endl;//输出最底的
	}
    return 0;//完结散花
}

彩蛋

这是我第一道没有任何人帮助的AC的DP题

点赞就祝你身体健康

注意！！！

因为是从北走到南，所以要倒着dp

#include<bits/stdc++.h>
using namespace std;
int arr[110][110],f[110][110];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cin>>arr[i][j];
        }
        memset(f,0,sizeof(f));
        arr[0][0]=0;
        for(int i=n;i>=0;i--){
            for(int j=m;j>=0;j--){
                f[i][j]=max(f[i+1][j],f[i][j+1])+arr[i][j];
            }
        }
        int maxx=-1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=n;j++)maxx=max(maxx,f[i][j]);
        }
        cout<<maxx<<'\n';
    }
    return 0;
}

A1284 摘花生

题意

见题目

底层逻辑

最短路径问题但是改版 具体表现为dp[j][k]=min(dp[j-1][k],dp[j][k-1])+c[j][k] (c为矩阵) 极端情况（如处于上边缘或侧边缘）需要单独考虑，具体见歹马19-27行

歹马

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		int a,b;
		cin>>a>>b;
		int c[a][b];
		int dp[a][b];
		memset(dp,0,sizeof(dp));
		for(int j=0;j<a;j++){
			for(int k=0;k<b;k++){
				cin>>c[j][k];
			}
		}
		for(int j=0;j<a;j++){
			for(int k=0;k<b;k++){
				if(j==0&&k==0){
					dp[j][k]=c[j][k];
				}
				else if(j==0&&k!=0){
					dp[j][k]=dp[j][k-1]+c[j][k];
				}
				else if(j!=0&&k==0){
					dp[j][k]=dp[j-1][k]+c[j][k];
				}
				else{
					dp[j][k]=max(dp[j-1][k],dp[j][k-1])+c[j][k];
				}
			}
		}
		cout<<dp[a-1][b-1]<<endl;
	}
	return 0;
}