yukicoder No.285〜No.287
解法
No.285 はタネあかしすると簡単で, 元の値段に 108 を掛けたあと, それを 100 で割った商が整数部分, 100 で割った余りが少数部分になります。
本番は何も考えず 1.08 を掛けたら通ってしまいました。
int main() { ll n; cin >> n; n *= 108; ll tmp = n%100; printf("%lld.%lld%lld\n", n/100, tmp/10, tmp%10); return 0; }
No.286 は bitDP で解けます。dp[s] = (s で表される分の商品を購入した時の最小負担額) とすると, 今までに買った商品の合計価格は s にのみ依存して決まるので, 割引される値段もわかり, bitDP で解けることがわかります。
const int MAXN = 16; const int INF = 1e9; int M[MAXN]; int dp[1<<MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; for (int i = 0; i < N; i++) cin >> M[i]; for (int i = 0; i < 1<<N; i++) dp[i] = INF; dp[0] = 0; for (int s = 0; s < 1<<N; s++) { if (dp[s] == INF) continue; int sum = 0; for (int i = 0; i < N; i++) if ((s>>i)&1) sum += M[i]; sum %= 1000; for (int i = 0; i < N; i++) { if ((s>>i)&1) continue; int ns = s|1<<i; int now = M[i]-sum; now = max(now, 0); dp[ns] = min(dp[ns], dp[s] + now); } } cout << dp[(1<<N)-1] << endl; return 0; }
No.287 は dp します。dp[m][sum] = (m 個目の時点で合計数が sum になっているような場合の数)としてがんばります。
ll dp[10][830]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; dp[0][0] = 1; for (int i = 0; i < 8; i++) { for (int j = 0; j <= 6*n; j++) { if (dp[i][j] == 0) continue; for (int k = 0; k <= n; k++) { dp[i+1][j+k] += dp[i][j]; } } } cout << dp[8][6*n] << endl; return 0; }