読者です 読者をやめる 読者になる 読者になる

JOI 2008 春合宿 day2-1 「Nile.com」

一発で通ったから気持ちよかった。
まぁ、DP臭しかしませんね。

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

const int INF = 100000000;

int dp[6000];


int main(){
	int n, d, a, wm = INF, nm;
	
	scanf("%d%d",&n,&d);
	
	rep(j,n){
		scanf("%d", &a);
		
		dp[j] = a;
		dp[j+3000] = INF;
		
		wm = min(wm,a);
	}
	
	
	d--;
	
	rep(i,d){
		nm = INF;
		
		rep(j,n){
			scanf("%d", &a);
			
			dp[j+3000] = min(dp[j] + a*9/10, dp[j+3000] + a*7/10);
			dp[j] = wm + a;
			
			nm = min(nm, min(dp[j], dp[j+3000]));
		}
		
		wm = nm;
	}
	
	printf("%d\n", nm);
	
	return 0;
}