幼儿园DP。
——代码
1 #include <cstdio> 2 #include <iostream> 3 4 const int MAXN = 2001; 5 int n, m, ans = ~(1 << 31); 6 int a[MAXN][MAXN], f[MAXN][MAXN]; 7 8 inline int read() 9 { 10 int x = 0, f = 1; 11 char ch = getchar(); 12 for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; 13 for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; 14 return x * f; 15 } 16 17 inline int min(int x, int y) 18 { 19 return x < y ? x : y; 20 } 21 22 int main() 23 { 24 int i, j; 25 n = read(); 26 m = read(); 27 for(i = 1; i <= m; i++) 28 for(j = 1; j <= n; j++) 29 a[i][j] = read(); 30 for(i = 1; i <= n; i++) 31 { 32 f[i][1] = min(f[i - 1][1], f[i - 1][m]) + a[1][i]; 33 for(j = 2; j <= m; j++) 34 f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + a[j][i]; 35 } 36 for(i = 1; i <= m; i++) ans = min(ans, f[n][i]); 37 printf("%d ", ans); 38 return 0; 39 }