AOJ_0106 Discounts of Buckwheat
久しぶりのDP。DPの考え方を一瞬わすれた。日頃からやっとかないとだめですね。
問題
これ
#include <cstdio> using namespace std; int t[]={ 0,0,380,550,760,850,1100,1230,1400,1610,1520,1950,1870, 2070,2250,2244,2620,2624,2794,3004,3040,3344,3390,3590, 3740,3764,4120,4114,4314,4494,4488,4864,4868,5038,5248, 5284,5588,5634,5834,5984,6008,6364,6358,6558,6738,6732, 7108,7112,7282,7492,7528 }; int main(){ int n; while(scanf("%d",&n)&&n){printf("%d\n",t[n/100]);} return 0; }
はどうやって作ったかと言うと、
#include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 30; const int ryou[] = { 2, 3, 5, 10, 12, 15}; const int val[] = {380, 550, 850, 1520, 1870, 2244}; int dp[51]; void solve(){ dp[0] = 0; dp[1] = INF; for(int i = 2; i <= 50; i++){ dp[i] = INF; for(int j = 0; j < 6; j++){ int k = i - ryou[j]; if(k < 0) break; dp[i] = min(dp[i], dp[k] + val[j]); } } } int main(){ int N; solve(); printf("#include <cstdio>\nusing namespace std;\n"); printf("int t[] = {\n"); for(int i = 0; i <= 50; i++){ printf("%d,", dp[i]); if(i % 10 == 9) printf("\n"); } printf("\n};"); return 0; }