| 로곡 | 동적 기획 | P1130 레드카드

1002 단어 낙곡동적 기획
https://www.luogu.org/problem/show?pid=1130
비교적 간단한 DP, i-1 방향으로 바꿀 수 없음
#include
#include
#include
#include
#define ms(i,j) memset(i,j, sizeof i);
/*	NOIP2016   ,RP++ 
	Luogu: P1130   
*/
using namespace std; 
int n,m;
int f[2005][1005];
int a[1005][2005];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1;i<=m;i++)
    for (int j=1;j<=n;j++)
    	scanf("%d", &a[i][j]);
    ms(f, 127);
    for (int i=1;i<=m;i++) f[1][i] = a[i][1];
	for (int i=2;i<=n;i++)
    for (int j=1;j<=m;j++)
    {
		if (j-1>0) f[i][j] = min(f[i][j], f[i-1][j-1]);//      
		if (j==1) f[i][j] = min(f[i][j], f[i-1][m]);//     ,          
		f[i][j] = min(f[i][j], f[i-1][j]);//     
		f[i][j] += a[j][i];//     
	}
	int ans = 100000000;
	for (int i=1;i<=m;i++) ans = min(ans, f[n][i]);
	printf("%d
", ans); return 0; } /* 4 3 1 8 9 4 2 2 7 7 6 5 7 1 */

좋은 웹페이지 즐겨찾기