第13回日本情報オリンピック 本選 「IOI饅頭」 AOJ0599 (IOI Manju)

DP

解説は下を参照してください。
http://www.ioi-jp.org/joi/2013/2014-ho/2014-ho-t2-review.pdf

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int m,n,ans;
int ma[10003];
int ha[503][2];
int dp[503][10003];
int main(){
	scanf("%d%d",&m,&n);
	for(int i = 0;i < m;i++){
		scanf("%d",&ma[i]);
	}
	sort(ma,ma + m,greater<int>());
	for(int i = 1;i < m;i++)ma[i] += ma[i-1];
	for(int i = 0;i < n;i++){
		scanf("%d%d",&ha[i][0],&ha[i][1]);
	}
	for(int i = 0;i <= n;i++){
		for(int j = 1;j <= m;j++){
			dp[i][j] = INF;
		}
	}
	for(int i = 1;i <= ha[0][0];i++){
		dp[1][i] = ha[0][1];
		ans = max(ans,ma[i-1]-dp[1][i]);
	}
	for(int i = 2;i <= n;i++){
		for(int j = 1;j <= m;j++){
			dp[i][j] = min(dp[i-1][j],ha[i-1][1]+dp[i-1][max(0,j-ha[i-1][0])]);
			ans = max(ans,ma[j-1]-dp[i][j]);
		}
	}
	printf("%d\n",ans);
	return 0;
}