JOI2011本戦 第二問「古本屋」
はい、今日もちょびちょび書いていきますよ〜
絶対DPは出るだろうと思ってたら案の定、出たっていう話ですね。
ただ、DPに至るまでにワンステップありましたね。
最初は、naiさんがおまけとして説明してた貪欲法かな〜、と思ったんですが割とすぐダメだと気付いた。
まあ、解説の第一段階として貪欲法での解き方(解けないけど)を。
貪欲法
ジャンルの概念を無視して考えるならば、
ソートをして高い本から順番に k 冊売ればいいですよね?
それを発展させて、
・ジャンルごとにソートをして、そのソート列に細工をして、貪欲法。
っていう方針を立てます。
「細工」とは?
ジャンル1の本が4冊あるとする。
それぞれの本の値段を、c1,c2,c3,c4とする。
1冊売ると c1円
2冊売ると c1+c2+(1×2)円
3冊売ると c1+c2+c3+(2×3)円
4冊売ると c1+c2+c3+c4+(3×4)円
になる。
ここで「同じジャンルの本が1冊増えると何円収入が増えるか」を考える。
1冊のときと2冊のときの差は、c2 + 2円
2冊のときと3冊のときの差は、c3 + 4円
3冊のときと4冊のときの差は、c4 + 6円
何となく法則性が見つけられますね。 つまり、
・i-1冊のときと i 冊のときの差は、ci + 2*(i-1)円
ってなわけです。
よって、「細工」とは
・ソート列の i 番目に、2*(i-1)を足す。
ですね。
というわけで、こういうソースが書けます。
#include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<functional> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) #define drep(i,n) for(int i = n; i >= 0; i--) #define pb push_back using namespace std; int main(){ int n, k, c, g, ans = 0, x, y; scanf("%d%d", &n, &k); vector<int> b[11]; queue<int> q[11]; rep(i,n){ scanf("%d%d",&c,&g); b[g].pb(c); } rrep(i,10) sort(b[i].begin(), b[i].end(), greater<int>()); rrep(i,10) rep(j,b[i].size()) q[i].push(b[i][j] + 2*j); rep(i,k){ x = 0; rrep(j,10){ if (!q[j].empty() && x < q[j].front()) { x = q[j].front(); y = j; } } ans += x; q[y].pop(); } printf("%d\n",ans); return 0; }
しかし、このソースだとしょっぱなからバグります。
7 4 14 1 13 2 12 3 14 2 8 2 16 3 11 2
この入力データの正解は60ですが、上のソースだと59になります。
何がおかしいのか、実験してみましょう。
まずはジャンルごとにソートします。
1 : 14 2 : 14 13 11 8 3 : 16 12
次に「細工」をします。
1 : 14 2 : 14 15 15 14 3 : 16 14
すると、ジャンル2が降順ではなくなっています!
これがバグを生み出しているんですね。
というわけで、貪欲法はうまくいきません。
ではどうするか。
とりあえず、データの持ち方を工夫しましょう。
すなわち、本それぞれの値段を記録するのではなく、
各ジャンルから i 冊買う時の最高の収入
を記録するのです。
上のサンプルデータだとこうなります。
1 : 14 2 : 14 29 44 58 3 : 16 30
さて、ここからどうするかというと、
DPです! 動的計画法です! ダイナミックプログラミングです!!
いや、まあつまり
ジャンル i までの本を j 冊売るときの最高の収入 でDPるんです!
DPが分からない人は、表紙に蟻が書いてある本でも読んでもらうとして、
最終的にはこうなります。
#include<cstdio> #include<algorithm> #include<vector> #include<functional> #define rep(i,n) for(int i = 0; i < n; i++) #define rrep(i,n) for(int i = 1; i <= n; i++) #define drep(i,n) for(int i = n; i >= 0; i--) #define pb push_back using namespace std; int dp[2000]; int main(){ int n, k, c, g; scanf("%d%d", &n, &k); vector<int> b[11], v[11]; rep(i,n){ scanf("%d%d",&c,&g); b[g].pb(c); } rrep(i,10){ sort(b[i].begin(), b[i].end(), greater<int>()); v[i].pb(0); } rrep(i,10) rep(j,b[i].size()) v[i].pb(v[i][j] + b[i][j] + j*2); rrep(i,10){ drep(j,k){ for(int h = max(0,j-(int)v[i].size()+1); h < j; h++){ dp[j] = max(dp[j], dp[h] + v[i][j-h]); } } } printf("%d\n",dp[k]); return 0; }
〜変数説明〜
dp[2000] : DPテーブル(再利用する) dp[j]は、j 冊売るときの最高の収入。
n, k, c, g : 入力用
b[11] : bookのb 各ジャンル(1~10)の本の値段を入力し、ソートする。
v[11] : valueのv v[i][j]は、ジャンル i の本を j 冊売るときの最高の収入。
というわけで、たぶんあと3日くらい続きま〜す/