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; }