一道ACM的题目 请人帮忙一下,我不知道错哪里了
http://acm.hdu.edu.cn/showproblem.php?pid=1248
#include <iostream>
using namespace std;
int main()
{
int money;
int j=-1;
cin> > j;
if(j> =1&&j <=100)
{
for(;j> 0;j--)
{
cin> > money;
if(money> =1&&money <=10000)
{
money=(((money%350)%200)%150);
cout < <money < <endl;
}
}
}
//system( "pause ");
}
以上是本人的代码
但是总是提交错误`~!!
请各位大大帮忙看看
[解决办法]
??
有错么?
我可以编译通过 运行正常
不知道要实现什么功能?
[解决办法]
没发现问题
[解决办法]
提交错误`~!~??
说的详细点嘛
[解决办法]
算法明显错误了,
如果money=450,答案应该是450-2*200=50;
按你的却是100
[解决办法]
动态规划题嘛
设f(n)为n元钱买东西所能剩下的最少钱数,则
f(n)=min{f(n-150),f(n-200),f(n-350)} n> =350
n-200 200 <=n <350
n-150 150 <=n <200
n 0 <=n <150
用递推解决
#include <iostream>
using namespace std;
int min(int i,int j,int k)
{
int temp;
if (i> j) temp=j;
else temp=i;
if(temp> k) temp=k;
return temp;
}
int main()
{
int money;
int num;
int i;
int f[10000];
for(i=0;i <150;i++)
{
f[i]=i;
}
for(i=150;i <200;i++)
{
f[i]=i-150;
}
for(i=200;i <350;i++)
{
f[i]=i-200;
}
for(i=350;i <=10000;i++)
{
f[i]=min(f[i-150],f[i-200],f[i-350]);
}
cin > > num;
for(i=1;i <=num;i++)
{
cin > > money;
cout < < f[money] < < endl;
}
return 0;
}
[解决办法]
楼上的去提交下,ac了就可以乐:)
[解决办法]
错,此题不能这么解,你的算法叫谈心法,非动态规划。
n=401
答案应该是
401 - 200 - 200
而不是
401 - 350
[解决办法]
void doit(int *ret, int n)
{
if (n < 150)
{
if (n < *ret)
{
*ret = n;
}
return;
}
if (n > 350)
{
doit(ret, n - 350);
}
if (n > 200)
{
doit(ret, n - 200);
}
doit(ret, n - 150);
}