2013-03-16 15:40:05Morris
[ZJ][DP] a646. 小民買糖果
內容 ：
某天某糖果店舉辦活動：集滿 n 張糖果包裝紙即可再多得一顆糖果。而 n 卻是由顧客由抽獎決定，這樣無良的老闆所設計出來的活動實在是讓店員很困擾，不知道該給客人幾顆糖果。希望你們寫個程式幫店員小姐解決這個問題。
原題如上描述
額外補充
然而這已經換成匯率問題，小民每次拿 n 張去兌換時，只能兌換 n * p (無條件捨去取整數) 個糖果，而此時換到的糖果也有包裝紙，又可以再次兌換，問一開始給小民 c 個糖果，根據匯率 p，小民最多能換到幾顆糖果。
輸入說明
：
正整數 c 代表顧客買幾顆糖果。
浮點數 p 介於 0 ~ 1，代表一張包裝紙可以換幾顆糖果。
0 < c < 1000, p 至多小數點三位
輸出說明
：
顧客最多能獲得幾顆糖果。
範例輸入 ：
15 0.2 15 0.3
範例輸出 ：
18 20
提示
：
出處
：
中央助教
(管理：morris1028)
方程:dp[n] = max(dp[n + floor(i*p) - i] + floor(i*p)), 0<i<=n,
狀態:dp[n] 表示 n 張包裝紙的最大糖果數，i 是拿多少去兌換。
因此最後輸出 dp[c]+c
不可以使用 double 型態去處理，會有誤差
/****************************************************************/
/* Problem: a646 "小民買糖果" from 中央助教 */
/* Language: CPP (1024 Bytes) */
/* Result: AC(224ms, 268KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-03-15 19:59:44 */
/****************************************************************/
#include <stdio.h>
#include <string.h>
int dp[1000], a, b;
int shift[1000], shift_v[1000];
char used[1000];
int build(int n) {
if(n == 0)
return 0;
if(used[n])
return dp[n];
int i, v, tmp;
dp[n] = 0;
for(i = shift[n]; i >= 1; i = shift[i-1]) {
v = shift_v[i];
tmp = build(v+n-i) + v;
if(tmp > dp[n])
dp[n] = tmp;
}
used[n] = 1;
return dp[n];
}
int main() {
int n, i, j, k;
char s[50];
while(scanf("%d %s", &n, &s) == 2) {
for(i = 2, a = 0, b = 1; s[i]; i++)
b *= 10, a = a*10 + s[i]-'0';
for(i = 1; i <= n; i++)
shift_v[i] = i*a/b;
for(i = n, k = n; i >= 0; i--) {
if(i == 0 || shift_v[i] != shift_v[i-1]) {
for(j = i; j <= k; j++)
shift[j] = i;
k = i-1;
}
}
memset(used, 0, sizeof(used));
printf("%d\n", build(n)+n);
}
return 0;
}