题解 P1130 【红牌】

发表于 更新于 阅读次数： Waline：
P1130 【红牌】题解。

纪念一下我做出的第一道DP题

此题很像数字三角形，只不过那题要求所经数值最大，这题最小。

~~ 话说我觉得并没有什么方程…… ~~

思路：从倒数第2步考虑，取两种方案中最小的一种，然后一直做到第一步，找最小值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int n,m,a[2005][2005],ans=1<<30;//ans必须要定大，不然找不到最小值
int main(){
    scanf ("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    for (int j=0;j<n;j++)scanf ("%d",&a[i][j]);
    for (int j=n-2;j>=0;j--)//从倒数第2步开始，向第一步推进
    //我用的是0下标
    for (int i=0;i<m;i++)
    a[i][j]=min(a[(i+1)%m][j+1],a[i][j+1])+a[i][j];//取最小值，更新为之后的步骤的最小值
    for (int i=0;i<m;i++)ans=min(ans,a[i][0]);//找答案
    printf ("%d",ans);//结束
    return 0;
}