8 条题解

  • 1
    @ 2023-1-9 14:16:07

    经典动态规划题,递归思考,递推解决。

    太经典,不做解释。

    代码如下:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1005;
    int a[N][N];
    int dp[N][N];
    int n;
    int main()
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	//DP
    	for(int i=n;i>=1;i--)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
    		}
    	}
    	cout<<dp[1][1];
    	return 0;
    }
    
    • 0
      @ 2025-9-21 20:18:14
      #include<bits/stdc++.h>
      using namespace std;
      const int N = 1e4 + 10;
      int r;
      int a[N][N],dp[N][N];
      int main(){
      	
      	cin >> r;
      	for(int i = 1;i <= r;i++){
      		for(int j = 1;j <= i;j++){
      			cin >> a[i][j];
      		}
      	}
      	for(int i = 1;i <= r;i++){
      		for(int j = 1;j <= i;j++){
      			dp[i][j] = max(dp[i - 1][j - 1],dp[i - 1][j]) + a[i][j];
      		}
      	}
      	int nmax = -1;
      	for(int i = 1;i <= r;i++){
      		nmax = max(nmax,dp[r][i]);
      	}
      	cout << nmax;
      	return 0;
      }
      
      • 0
        @ 2023-9-17 17:18:22
        using namespace std;
        int x,y,a[1001][1001];
        int main(){
        	cin >> x;
        	for(int i = 1 ; i <= x ; i++){
        		for(int j = 1 ; j <= i ; j++) cin >> a[i][j];
        	}
        	for(int i = 1 ; i <= x ; i++){
        		for(int j = 1 ; j <= i ; j++) a[i][j] += max(a[i-1][j],a[i-1][j-1]);
        	}
        	for(int i = 1 ; i <= x ; i++){
        		y = max(y,a[x][i]);
        	}
        	cout << y << endl;;
        }
        
      • 0
        @ 2023-2-24 18:50:19

        这题是道动规题因为标签是动规...啊啊啊放错了

        这题是求从起点到终点的最大路径,每个点不受其它点的影响,无后效性,所以是动态规划题。(这才对嘛

        • 首先确定dp数组含义,这里dp[i]含义是从起点到i点的最大路径和。
        • 其次确定状态转移方程,dp[i][j]可由dp[i-1][j]或dp[i-1][j-1]得到。于是我们的状态转移方程为:dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i][j];
        • 再次是初始化,dp[1][1]=a[1][1],dp数组中其它的不用初始化,等于什么都可以。
        • 最后是遍历顺序,按题目中说的二维三角形来。
        • 众所周知,节俭是个好习惯,所以我们的dp数组和a数组只用开25*25!

        蒟蒻の代码:

        #include <iostream>
        #include <queue>
        #include <cstdio>
        using namespace std;
        
        int dp[1001][1001],a[1001][1001],ans,n;
        
        int main()
        {
            int n;
            cin >> n;
            for(int i = 1;i <= n;i++)
            {
                for(int j = 1;j <= i;j++)
                {
                    cin >> a[i][j];
                }
            }
            dp[1][1] = a[1][1];//初始化
            for(int i = 1;i <= n;i++)
            {
                for(int j = 1;j <= i;j++)
                {
                    dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - 1]) + a[i][j];//转移方程
                    ans = max(ans,dp[i][j]);
                }
            }
            cout << ans;
            return 0;
        }
        

        这题!也可以用递归做!🙂

        代码:

        #include <iostream>
        using namespace std;
        
        bool is[1001][1001];
        int a[1001][1001],f[1001][1001],n,ans;
        
        int dfs(int x,int y)
        {
        	if(x == 1)
        	{
        		return a[1][1];
        	}
        	if(is[x][y])
        	{
        		return f[x][y];
        	}
        	is[x][y] = true;
        	f[x][y] = max(dfs(x - 1,y),dfs(x - 1,y - 1)) + a[x][y];
        	
        	return f[x][y];
        }
        int main()
        {
            cin >> n;
            for(int i = 1;i <= n;i++)
            {
                for(int j = 1;j <= i;j++)
        		{
        			cin >> a[i][j];
        		}
            }
            for(int i = 1;i <= n;i++)
            {
                ans = max(ans,dfs(n,i));
            }
            cout << ans;
            return 0;
        }
        
        • 0
          @ 2022-3-5 19:07:15
          #include <iostream>
          #include <stdio.h>
          #include <string.h>
          #include <queue>
          #include <math.h>
          #include <vector>
          #include <algorithm>
          #include <iomanip>
          #include <stack>
          
          using namespace std;
          
          #define LL long long
          const int N =1e5+10;
          const int INF =0x3f3f3f3f;
          int a[3000][3000];
          int r,ans;
          int main(){
          	cin>>r;
          	for(int i=1;i<=r;i++){
          		for(int j=0;j<i;j++){
          			cin>>a[i][j];
          			a[i][j]+=max(a[i-1][j],a[i-1][j-1]);
          			ans=max(ans,a[i][j]);
          		}
          	}
          	cout<<ans<<endl;
          	return 0;
          }
          • 0
            @ 2022-1-16 11:28:41

            #include using namespace std; int n,a[1001][1001],maxn; int main() { cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ a[i][j]+=max(a[i-1][j],a[i-1][j-1]); } } for(int i=1;i<=n;i++){ maxn=max(maxn,a[n][i]); } cout<<maxn; }

            • 0
              @ 2022-1-16 11:28:23

              #include using namespace std; int n,a[1001][1001],maxn; int main() { cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ cin>>a[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ a[i][j]+=max(a[i-1][j],a[i-1][j-1]); } } for(int i=1;i<=n;i++){ maxn=max(maxn,a[n][i]); } cout<<maxn; }

              • 0
                @ 2021-10-10 10:40:57
                #include <iostream>
                #include <algorithm>
                using namespace std;
                const int N = 1e3 + 10; 
                int a[N][N];
                int main(){
                	int n;
                	cin >> n;
                	for(int i = 1; i <= n; i++){
                		for(int j = 1; j <= i; j++){
                			cin >> a[i][j];
                		}
                	}
                	for(int i = 1; i <= n; i++){
                		for(int j = 1; j <= i; j++){
                			a[i][j] = max(a[i-1][j-1], a[i-1][j]) + a[i][j];
                		}
                	}
                	int maxx = 0;
                	for(int i = 1; i <= n; i++){
                		maxx = max(maxx, a[n][i]);
                	}
                	cout << maxx << endl;
                }
                
                • 1

                信息

                ID
                561
                时间
                1000ms
                内存
                256MiB
                难度
                5
                标签
                递交数
                638
                已通过
                225
                上传者