内容敏感图像压缩
Background
在清华大学存活，你需要有极强的文献阅读能力……【该背景与本题无关】
Description
有一张N*M的方格纸，每一个格子上写了一个正整数，现在我们把方格纸首尾相连，组成一个高度为N，周长为M的圆柱体的侧表面。
现在你需要找到一个从上到下贯穿该圆柱侧表面的长度为N的路径，使得路径上的权值尽量小。其中，路径上相邻的两点必须是“八连通的”。
Input Format
第一行两个整数N，M。接下来若干行是一个N* M的矩阵
Output Format
一行一个整数，表示答案。
Sample Input
3 3
1 2 2
2 2 1
3 2 1
Sample Output
3
Constraint
·对于20%数据，min(N,M) = 1
·对于40%数据N,M <= 40
·对于约50%数据，路径不经过圆柱体侧表面。
·对于100%数据，N,M <= 3000
所以，这道题的名字有什么意义呢？可以考完试看一看题目后面附的文章。(文章里有答案，我却没有看，不过就算看了我也不会写qaq)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 3010
#define INF 0x3f3f3f3f
int dp[MAXN][MAXN*2];
int mat[MAXN][MAXN*2];
int nextInt() {
int ans=0;
char c = 0;
while (c=getchar(),c<'0'||c>'9');
while (ans = ans*10+c-'0',c=getchar(),c>='0' && c<='9');
return ans;
}
int main() {
//freopen("compress.in","r",stdin);
//freopen("compress.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
memset(mat,0x3f,sizeof(mat));//把每个值都初始为最大值
memset(dp,0x3f,sizeof(dp));
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
int x;
x = nextInt();//快读
mat[i][j] = mat[i][j + m] = x;//分环成链
}
for(int j = 1;j <= m;j++)
dp[0][j] = 0;//假设上面有一行全为 0的
for(int i = 1;i < = n;i++)
for(int j = 1;j <= m*2;j++)
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1])) + mat[i][j];//动态规划求最短路径
int ans = INF;
for (int j = 1;j <= m*2;j++)
ans = min(ans,dp[n][j]);//通过比较找出最后一行的最小值
printf("%d ",ans);
return 0;
}