yukicoder : No.247 線形計画問題もどき

TCOに備えて早く寝る位の計画性が欲しい。
http://yukicoder.me/problems/678

問題

整数列A[i]に対し、関数fは以下のように定義される。
とする。
かつx[i]が非負整数という条件におけるx[i]の総和の最小値を求めよ。

解法

となるようなx[i]の総和の最小値をdp[P]とする。
dp[P]=min(dp[P],dp[P-A[i]]+1)の式でDPしてdp[C]を答えればよい。

int C,N;
int A[201010];
int dp[201010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>C>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,C+1) dp[i]=101010;
	dp[0]=0;
	FOR(i,N) FOR(j,C+1) dp[j+A[i]]=min(dp[j+A[i]],dp[j]+1);
	
	if(dp[C]>101000) dp[C]=-1;
	cout<<dp[C]<<endl;
}

まとめ

午前中からTCOオンサイト参加される方々は、ゆっくり休んで頑張ってください。