第7回日本情報オリンピック 春合宿 2日目 「Nile.com」

典型DP
予選で出てもおかしくないレベルなので解説は割愛。

#include <○○○○>や、using namespace std;は省略することにしました。

const int INF = 1000000000;
int n,d;
int dp[400][3002][3];
int p[400][3002];
int main(){

	scanf("%d%d",&n,&d);
	for(int i = 0;i <= d;i++){
		for(int j = 0;j <= n;j++){
			for(int k = 0;k <= 2;k++)dp[i][j][k] = INF;
		}
	}
	for(int i = 1;i <= d;i++){
		for(int j = 1;j <= n;j++){
			scanf("%d",&p[i][j]);
		}
	}
	for(int i = 1;i <= n;i++){
		dp[1][i][0] = p[1][i];
	}
	for(int i = 2;i <= d;i++){
		int ki = INF;
		for(int j = 1;j <= n;j++){
			ki = min(min(ki,dp[i-1][j][0]),min(dp[i-1][j][1],dp[i-1][j][2]));
		}
		for(int j = 1;j <= n;j++){
			dp[i][j][0] = ki + p[i][j];
			dp[i][j][1] = dp[i-1][j][0] + (p[i][j] * 9 / 10);
			dp[i][j][2] = min(dp[i-1][j][1],dp[i-1][j][2]) + (p[i][j] * 7 / 10);
		}
	}

	int ans = INF;

	for(int i = 1;i <= n;i++){
		ans = min(min(ans,dp[d][i][0]),min(dp[d][i][1],dp[d][i][2]));
	}

	printf("%d\n",ans);

	return 0;
}