柱爷的下凡

Time Limit: 400/400MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit  Status

下凡的柱爷想只创造3种硬币，要求这3种硬币可以组成 [1,N] [1,N]的所有整数，并且表示一个 [1,N] [1,N]中的整数所用硬币的平均数量最少.

你能帮柱爷解决他的小小问题吗？

Input

第一行一个正整数 T T,表示测试组数.

接下来 T T行,每行一个正整数 N N.

数据保证:

1≤T≤200 1≤T≤200

1≤N≤200 1≤N≤200

Output

输出一共有 T T行,每行三个整数 A A  B B  C C表示柱爷希望的三种不同硬币的面值.如果有多组解,请保证A尽可能小,如果仍有多组解,请保证B尽量小,如果仍有多组解,请保证C尽量小.  A<B<C A<B<C

Sample input and output

Sample Input Sample Output 1 1 1 2 3 1 7 1 2 5

Hint

当 N=7 N=7时

1 1元,需要 1 1个 1 1元 2 2元,需要 1 1个 2 2元 3 3元,需要 1 1个 1 1元和 1 1个 2 2元 4 4元,需要 2 2个 2 2元 5 5元,需要 1 1个 5 5元 6 6元,需要 1 1个 1 1元和 1 1个 5 5元 7 7元,需要 1 1个 2 2元和 1 1个 5 5元平均需要约 1.57 1.57个硬币.

Source

2016 UESTC Training for Dynamic Programming

题解：感觉是个暴力枚举+背包，暴力枚举所有组合情况，然后背包实现硬币统计。

代码如下：

#include <iostream> #include <bits/stdc++.h> using namespace std; int dp[205][205][205]; int coin[205][3]; //double eps=1e-7; int main() { int T; cin>>T; int n; int ans[3]; ans[0]=1; ans[1]=2; ans[2]=3; for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) for(int k=0;k<=n+1;k++) dp[i][j][k]=205; for(int i=2;i<=200;i++) { ans[1]=i; for(int j=i+1;j<=200;j++) { ans[2]=j; int now=0; dp[i][j][0]=0; for(int k=1;k<=200;k++) { if(k==1) dp[i][j][k]=1; else if(k>1&&k<ans[1]) dp[i][j][k]=dp[i][j][k-ans[0]]+1; else if(k>=ans[1]&&k<ans[2]) dp[i][j][k]=min(dp[i][j][k-ans[0]],dp[i][j][k-ans[1]])+1; else dp[i][j][k]=min(dp[i][j][k-ans[2]],min(dp[i][j][k-ans[1]],dp[i][j][k-ans[0]]))+1; //now+=dp[i][j][k]; } } } for(int N=1;N<=200;N++){ int minn=100000; coin[N][1]=2; coin[N][2]=3; for(int k=2;k<=N-1;k++){ for(int j=k+1;j<=N;j++){ int sum=0; for(int n1=1;n1<=N;n1++){ sum+=dp[k][j][n1]; } if(minn>sum) { minn=sum; coin[N][1]=k; coin[N][2]=j; } } } } while(T--) { cin>>n; cout<<'1'<<' '<<coin[n][1]<<' '<<coin[n][2]<<endl; } //cout << "Hello world!" << endl; return 0; }