为什么组数和步数要反过来动规?
  • 板块P1130 红牌
  • 楼主zmrlcwds
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/3/5 00:11
  • 上次更新2023/10/23 23:02:14
查看原帖
为什么组数和步数要反过来动规?
278914
zmrlcwds楼主2023/3/5 00:11

因为我自己思考的时候是想的 dp[i][j]表示前i组完成前j步需要的最小步数 这个和大家想的都一样,我就按照惯性思维进行先组后步骤进行遍历求解 下面是我的代码, 之后wa了两个点 我想不出哪有问题,然后看了一下题解发现大家都是先n 后m 我还是有点想不通为什么我这个不行

#include <iostream>
#include <string.h>
#define INF 100000000
using namespace std;

int n, m;
int arr[ 2005 ][ 2005 ];
long long dp[ 2005 ][ 2005 ];
int main() {
  cin >> n >> m;
  for ( int i = 1; i <= m; i++ ) {
    for ( int j = 1; j <= n; j++ ) {
      cin >> arr[ i ][ j ];
    }
  }
  /*
    dp[i][j] 表示 前i组完成前j步最少使用的天数
      从本组上一步来的 dp[i][j-1]
      从上一组的上一步来的 dp[i-1][j-1]
    dp[i][j] = min(dp[i][j-1], dp[(i-1+m)%m+1][j-1]) + arr[i][j];
  */
  for ( int i = 1; i <= n; i++ ) dp[ 1 ][ i ] = arr[ 1 ][ i ];
  for ( int k = 1; k <= 2; k++ ) {
    for ( int i = 2; i <= m + 1; i++ ) {
      int temp = i <= m ? i : 1;
      for ( int j = 1; j <= n; j++ ) {
        dp[ temp ][ j ] =
            min( dp[ temp ][ j - 1 ], dp[ i - 1 ][ j - 1 ] ) + arr[ temp ][ j ];
      }
    }
  }
  // cout << "-------------------------" << endl;
  long long minx = INF;
  for ( int i = 1; i <= m; i++ ) {
    minx = min( dp[ i ][ n ], minx );
  }
  cout << minx;
}

2023/3/5 00:11
加载中...