蓝桥杯 18省赛 C10 耐摔指数(dp)

蓝桥杯 18省赛 C10 耐摔指数(dp)

标题：耐摔指数

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

输入数据，一个整数n（3<n<10000）,表示测试塔的高度。
输出一个整数，表示最多测试多少次。

例如：
输入：
3

程序应该输出：
2

解释：
手机a从2楼扔下去，坏了，就把b手机从1楼扔；否则a手机继续3层扔下

再例如：
输入：
7

程序应该输出：
3

解释：
a手机从4层扔，坏了，则下面有3层，b,c 两部手机2次足可以测出指数；
若是没坏，手机充足，上面5,6,7 三层2次也容易测出。

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

---

笨笨有话说：
我觉得3个手机太难了，要是2个手机还可以考虑一下。

歪歪有话说：
想什么呢，你！要是1部手机还用你编程啊？那样的话只好从下往上一层一层测。

==================

思路:
每次丢手机,不管手机碎没碎->楼层都一分为二->不同的楼层划分策略,结果也不尽相同->想到这里,dp呼之欲出
题目说要找最坏情况和最好的策略->设手机i层丢下有两种局面:那么可知最坏情况->Math.max(手机碎了,没碎),最好情况->Math.min(dp滚动至前一次的最少次数 +1,最坏情况)

public class Main {
	static int[][] dp;
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n =sc.nextInt();
		sc.close();
		
		dp =new int[n +1][4];
		
		//只有一部手机时的最好情况
		for(int i =1 ;i <=n ;i ++) dp[i][1] =i;
 		//依次滚动到2部3部手机的最好情况
		for(int j =2 ;j <=3 ;j ++) 
			for(int i =1 ;i <=n ;i ++) {	//根据前一次(手机剩余数量还是跟之前一样)结果将每一个楼层丢手机(楼层划分)的的保底情况找出来
				dp[i][j] =dp[i -1][j] +1;	
				////找到最坏情况
				for(int k =2 ;k <=i ;k ++) {	
					dp[i][j] =Math.min(dp[i][j], Math.max(dp[k -1][j -1], dp[i -k][j]) +1);	//后面的'+1'是因为,按截点k分区的时候就有一次摔手机了
				}
			}
		
		System.out.println(dp[n][3]);
	}

}