UPC 2195 Temple Build(DP)
6079 ワード
午后、列挙の順番に注意しなければなりません....そしてデータ型....
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <queue>
5 #include <map>
6 #include <ctime>
7 #include <cmath>
8 #include <algorithm>
9 using namespace std;
10 #define LL long long
11 LL dp[1000001];
12 LL c[4];
13 LL h,top,bot,i;
14 LL judge(LL x)
15 {
16 double ans;
17 ans = (bot-top)*x*1.0/h;
18 ans = bot - ans;
19 ans /= c[i];
20 return (int)ans;
21 }
22 int main()
23 {
24 int j;
25 LL ans;
26
27 while(cin>>h>>bot>>top)
28 {
29 memset(dp,0,sizeof(dp));
30 for(i = 1; i <= 3; i ++)
31 cin>>c[i];
32 for(j = 1; j <= h; j ++)
33 {
34 for(i = 1; i <= 3; i ++)
35 {
36 int tt;
37 tt = judge(j);
38 if(j < c[i]) continue;
39 if(dp[j] < dp[j-c[i]] + (LL)c[i]*c[i]*c[i]*tt*tt)
40 {
41 dp[j] = dp[j-c[i]] + (LL)c[i]*c[i]*c[i]*tt*tt;
42 }
43 }
44 }
45 ans = 0;
46 for(i = 1; i <= h; i ++)
47 {
48 ans = max(ans,dp[i]);
49 }
50 cout<<ans<<endl;
51 }
52 return 0;
53 }