2 solutions

  • 2
    @ 2021-11-8 20:50:23

    这是一个dp板子题,可以百度dp或动态规划自行学习,要注意的点就是第一行和第一列的处理,因为只能向右向下,所以第一行和第一列每一格假如要走的步数只能由前一格推来,只有一个方向,状态转移方程比较好找,不懂的可以对照样例手推,并且要对数组初始化。

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N = 200;
    
    int dp[N][N],a[N][N];
    int n,m;
    
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--) {
    		scanf("%d%d",&n,&m);
    		memset(dp,0,sizeof dp);
    		for(int i = 1;i <= n; ++i) {
    			for(int j = 1;j <= m; ++j) {
    				scanf("%d",&dp[i][j]);
    			}
    		}
    		for(int i = 1;i <= n; ++i) dp[i][1] += dp[i-1][1];
    		for(int i = 1;i <= m; ++i) dp[1][i] += dp[1][i-1];
    		for(int i = 2;i <= n; ++i) {
    			for(int j = 2;j <= m; ++j) {
    				dp[i][j] += min(dp[i - 1][j],dp[i][j - 1]);
    			}
    		}	
    		printf("%d\n",dp[n][m]);
    	}
    		
    	return 0;
    }
    
    • 2
      @ 2021-11-7 23:02:58
      #include <iostream>
      using namespace std;
      const int N=1e8 + 5;
      int num[1010][1010],dp[1010][1010];
      int main() {
      	int t, n, m;
      	for (int i = 0; i <= 100; i++) num[i][0] =num[0][i] =dp[i][0] =dp[0][i] = N;
      	cin >> t;
      	while (t--) {
      		cin >> n >> m;
      		for (int i = 1; i <= n; i++)
      			for (int j = 1; j <= m; j++)
      				cin >> num[i][j];
      		for (int i = 1; i <= n; i++)
      			for (int j = 1; j <= m; j++) {
      				if (i == 1 && j == 1) dp[1][1] = num[1][1];
      				else dp[i][j] = min(dp[i][j - 1] + num[i][j], dp[i - 1][j] + num[i][j]);
      			}
      		cout << dp[n][m] << endl;
      	}
      	return 0;
      }
      
      • 1

      Information

      ID
      154
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      5
      Tags
      # Submissions
      39
      Accepted
      16
      Uploaded By