最小成本 WA40分求调!!!

常宸睿 · 2025 年7 月 13 日 08:20

3. 最小成本

题目ID：19502 必做题文件操作 100分

题目描述

对于被某个装置捉弄之后，小信决定利用他的魔法技能来改变现实以迅速逃脱。
你得到一个nn行 mm列的非负整数网格，以及一个整数 kk。我们用 (i,j)(i,j)表示从上到下第 ii行、从左到右第 jj列的单元格 (1\leq i \leq n,1\leq j \leq m)(1≤i≤n,1≤j≤m)。在每个单元格 (i,j)(i,j)上都有一个整数 a_{i,j}ai,j。
你起始位置于 (1,1)(1,1),目标是走到 (n,m)(n,m)。在移动过程中，你只能向下或向右移动———— 也就是说，如果你在 (i,j)(i,j),只能移动到 (i+1,j)(i+1,j)或者（i,j+1）, 当前，前提是这些单元格必须存在。
在开始移动之前，你可以进行以下操作任意多次：
从 11到 nn中任意选择一个整数 ii,然后将第 ii行的元素循环左移一位。这个操作的效果是，将每个 a_{i,j}ai,j更新为 a_{i,(j\ mod\ m)+1}ai,(j mod m)+1。
请注意，一旦你开始移动，就不能再进行行移操作。从 (1,1)(1,1)到 (n,m)(n,m)之后，令 xx是你在开始移动之前进行的操作次数，而 yy是你经过的所有单元格上的整数之和 (包括起始位置和目标位置)。最终成本被定义为 kx+ykx+y。
你的任务是计算出以最小成本从(1,1)(1,1)移动到 (n,m)(n,m)所需的操作次数。
大数据包在题目附件处下载。

输入格式

输入包括多个测试用例。第一行为测试用例数量 tt。
接下来每个测试用例包含：
一行三个用空格分隔的整数 n,m和 kn,m和k。
随后的 nn行，每行包含 mm个用空格分隔的整数，分别表示这一行上的a_{i,1},a_{i,2},…,a_{i,m}ai,1,ai,2,…,ai,m。
所有测试用例的 nmn∗m的总和不超过 510^45∗104。

输出格式

对于每个测试用例，输出从起点 (1,1)(1,1)到终点 (n,m)(n,m)的最小成本。

样例

Input 1

2
3 3 5
1 2 3
4 5 6
7 8 9
5 5 1000
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

Output 1

21
19

数据范围

对于 2020% 的数据：
t = 1。
1\leq n,m \leq 200,0\leq k \leq 10^91≤n,m≤200,0≤k≤109。
所有的 a_{i,j}ai,j都相同。
对于 2020% 的数据：
1\leq n,m \leq 4,0\leq k \leq 10^91≤n,m≤4,0≤k≤109。
0\leq a_{i,j} \leq 10^90≤ai,j≤109。
对于 100100%的数据：
1\leq t \leq 10^41≤t≤104。
1\leq n,m \leq 200,0\leq k \leq 10^91≤n,m≤200,0≤k≤109。
0\leq a_{i,j} \leq 10^90≤ai,j≤109。

附件

minimum cost.zip

#include <bits/stdc++.h>
using namespace std;
long long t,n,m,k,a[205][205],dp[205][205][205];
int main(){
  freopen("D.in","r",stdin);
  freopen("D.out","w",stdout);
  cin >> t;
  while(t--){
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i++){
      for(int j = 1;j <= m;j++){
        cin >> a[i][j];
      }
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i = 1;i <= n;i++){
      for(int j = 1;j <= m;j++){
        if(i-1 && j-1){
          dp[i][j][0] = min(dp[i-1][j][0],dp[i][j-1][0]) + a[i][j];
        }else if(i-1){
          dp[i][j][0] = dp[i-1][j][0] + a[i][j];
        }else if(j-1){
          dp[i][j][0] = dp[i][j-1][0] + a[i][j];
        }else{
          dp[i][j][0] = a[i][j];
        }
        //cout << dp[i][j][0] << " ";
        for(int l = 1;l < m;l++){
          if(i-1 && j-1){
            dp[i][j][l] = min(dp[i-1][j][l],dp[i][j-1][l])+a[i][j%m+l]+k*l;
          }else if(i-1){
            dp[i][j][l] = dp[i-1][j][l]+a[i][j%m+l]+k*l;
          }else if(j-1){
            dp[i][j][l] = dp[i][j-1][l]+a[i][j%m+l]+k*l;
          }else{
            dp[i][j][l] = a[i][j%m+l]+k*l;
          }
          //cout << dp[i][j][l] << " ";
        }
        //cout << endl;
      }
      //cout << endl;
    }
    long long minn = dp[n][m][0];
    for(int i = 1;i < m;i++){
      minn = min(minn,dp[n][m][i]);
    }
    cout << minn << endl;
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

冯俊骁 · 2025 年7 月 13 日 11:40

呦呦呦， @常宸睿居然发论坛了

最小成本 WA40分 求调!!!