首页 > 搜索 > DFS搜索 > HDU 3181-Greatest Naruto Army-动态规划-[解题报告]HOJ
2014
03-06

HDU 3181-Greatest Naruto Army-动态规划-[解题报告]HOJ

Greatest Naruto Army

问题描述 :

Wyb is a VERY VERY BIG fans of Naruto(漩涡鸣人). Naruto’s perseverance and passion attract him a lot, so does Naruto’s skill "Kagebunsin no jyutu"(影分身术). Actually, wyb knows more details about "Kagebunsin no jyutu" than most of us. When Naruto makes an new illusion(幻象), his Chakra will divide into two parts A and B, and increase Naruto’s weariness value by absolutely value of (A – B).
For example, at first Naruto have 5 Chakra, then he makes an illusion who has 2 Chakra. So he left 3 Chakra, and increase his weariness value by 1 (3 – 2). If he make a new illusion again and give him 2 Chakra, then he only left 1 Chakra and his weariness value changes to 2. Naruto cannot make a new illusion unless his Chakra is bigger than 1. What’s more, Naruto’s illusion can also use "Kagebunsin no jyutu" and the weariness they gains will also return to Naruto himself.
Furion's Sprout

Now Naruto wants to make as many illusions as he can because Kakashi Sensei wants to teach him a new Ninjyutsu(忍术) and minimum his weariness value.

输入:

The first line of input contains an integer T, indicating the number of test cases, then T lines follow , each line contains a positive integer N, indicating the number of Naruto’s Chakra.
0 < N < 10000000;

输出:

The first line of input contains an integer T, indicating the number of test cases, then T lines follow , each line contains a positive integer N, indicating the number of Naruto’s Chakra.
0 < N < 10000000;

样例输入:

2
5
9

样例输出:

2
3

http://acm.hdu.edu.cn/showproblem.php?pid=3181

这个题目一开始做,直接定义了一个10000000的数组,结果超了内存,后来自己改成了5000000的内存,过是能过,但内存还是用了很多。后来庄牛给了个递归的做法,我才发现的基础功很差。
#include
<iostream>
using namespace std;
int dp[100001];
int dfs(int
n)
{
if(n<100001&&dp[n]!=-1)
{
return dp[n];
}
if (n<100001)
{
if (n%2==0)
return dp[n] =
2*dfs(n/2);
else
return dp[n] =
dfs(n/2)+dfs(n-n/2)+1;
}
else
{
if (n%2==0)
return 2*dfs(n/2);
else
return dfs(n/2)+dfs(n-n/2)+1;
    }
}
int main()
{
memset(dp,-1,sizeof(dp));
dp[0]=dp[1]=dp[2]=0;
int t,n;
scanf(“%d”,&t);
while(t–)
{
scanf(“%d”,&n);
printf(“%d\n”,dfs(n));
}
return 0;
}
参考:http://blog.sina.com.cn/s/blog_64107d290100hppl.html


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept