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

JOI 2010/2011

今日の13:00 ~ 16:00にあったので出てきました。提出ミスが無ければ、

20 + 20 + 20 + 8 + 20 + 0 = 88.

本選行けるといいんだけど……。

今回特に悔しいのが問4.コンテスト中にDPを思いつかなかった。DPホント苦手。

終わってチャットとかしてたら、みんな解けててびっくりした。

僕は何してたかっていうと、DP考える時間なくて5分くらいでDFS書き上げて[入力1,2]だけ提出した。

あとでみんなの話とか聞いて解いてみたら典型的DPだったぽい。なぜ気づかなかったんだ・・・。

コンテスト後、満点解法であろうものを自分でも書いてみた。

問4(C++)

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	long long dp[100][21] = {0};
	
	int D; cin >> D; D--; 
	vector<int> data(D); rep(i,D) cin >> data[i];
	int n; cin >> n; 
	
	dp[0][data[0]] = 1;
	
	for(int i = 1 ; i < D; i++){
		rep(j,21){
			if( j-data[i] >= 0 ) dp[i][ j-data[i] ] += dp[i-1][j];
			if( j+data[i] <= 20) dp[i][ j+data[i] ] += dp[i-1][j];
		}
	}
	cout << dp[D-1][n] << endl;
}