第一场排位赛G.Bend Test

第一场排位赛G.Bend Test

思路

重点在于理解题目的状态转移方程、子问题的解、初始值？

转移方程

However, in the case where he has 2 prototypes (p=2, m=100 still) and tried the first for a pressure value x, if it bends then he is in the case where he has one prototype remaining and he has to test it for values from 1 to x-1 in sequence, yielding x tests in total in the worst case (the first prototypes tested once,the second at most x-1). However, if the first prototype does not beak when tested for value x, he reduced the problem to test pressure values from x+1 to 100 (we must keep in mind that he used one test).
我们设状态函数为(p,x)，那么转移方程就为(p,x)<-----max( (p-1,x)//折断 , (p,m-x)//未折断 ）+ 1
理解这句话：in result the minimum number of tests, in the worst case, is the minimum over all x.
即把测试的p全部耗尽的所用测试次数的最小值，即每次转移时我们要取最大值(测试完最坏的情况)，再取最小值。

关于初始化：

当p=1时，对于j任意值，最坏情况都是测试j-1次，
当j=1时，对于任意p，都不需要测试就可以知道，即0次。
而其他情况，因为最初的解一定是从p=1转移而来（不能从其他问题转移），所以我们设为无穷大。

代码

#include
using namespace std;
const int N = 51;
const int M =1001;
int dp[N][M];
void init ()
{
	memset(dp,0x3f,sizeof dp);
	for(int i=1;i>c;
	for(int k=1;k<=c;k++)
	{
		int p,m;
		cin>>p>>m;
		cout<<"Case "<