class Solution {
public:
    int ans[101][10001];
    Solution(){
        for(int i=0;i<101;i++)for(int j=0;j<10001;j++)ans[i][j]=0;
    }
    int superEggDrop(int k, int n) {
        if(ans[k][n])return ans[k][n];
        if(k==1)return n;
        if(n==0)return 0;
        ans[k][n]=n;
        int low=1,high=n;
        while(high-low>5){
            int m=(low+high)/2;
            if(superEggDrop(k-1,m-1)>superEggDrop(k,n-m))high=m;
            else low=m;
        }
        for(int i=low;i<=high;i++)ans[k][n]=min(ans[k][n],1+max(superEggDrop(k-1,i-1),superEggDrop(k,n-i)));
        return ans[k][n];
    }
};

PS：

需要用二分才能降低时间复杂度，而且不能用三分

CSU 1899: Yuelu Scenes（空间压缩）

题目：

Description
An artist begins with a roll of ribbon, one inch wide. She clips it into pieces of various integral lengths, then aligns them with the bottom of a frame, rising vertically in columns, to form a Yuelu scene. A Yuelu scene must be uneven; if all columns are the same height, it’s a plain scene, not a Yuelu scene! It is possible that she may not use all of the ribbon.

If our artist has 4 inches of ribbon and a 2 × 2 inch frame, she could form these scenes:

She would not form these scenes, because they're plains, not mountains!

Given the length of the ribbon and the width and height of the frame, all in inches, how many different Yuelu scenes can she create? Two scenes are different if the regions covered by ribbon are different. There’s no point in putting more than one piece of ribbon in any column.

Input
Each input will consist of several case. Each input will consist of a single line with three space-separated integers n, w and h, where n (0 n ≤ 10,000) is the length of the ribbon in inches, w (1 ≤ w ≤ 100) is the width and h (1 ≤ h ≤ 100) is the height of the frame, both in inches.

Output
Output a single integer, indicating the total number of Yuelu scenes our artist could possibly make, modulo 1e9 + 7.

Sample Input
25 5 5
15 5 5
10 10 1
4 2 2
Sample Output
7770
6050
1022
6

题目意思是说，在宽w高h的矩形里面放格子，格子数量不超过n，问有多少种放法使得不是每一列都完全一样高。

其实只要求出所有的放法，再减去一样高的放法就可以了。

考虑在宽i(i从1到w)高h的矩形格子里面放j个格子有多少种方法，用ans[i][j]表示

那么ans[i][j]=ans[i][j-1]+ans[i-1][j]-ans[i-1][j-h]

数组越界的按0算，当然，编程要保证不会越界。

这样，ans[w][0]+ans[w][1]+......+ans[w][n]就是所有的放法，再减去一样高的放法就可以了。

用了动态规划的空间压缩（刷表），所以代码不太好看懂。

代码：

#include<iostream>
using namespace std;
 
int ans[10001],p=1000000007;
 
int main()
{
	int n,w,h;
	while(cin>>n>>w>>h)
	{	
		if(n>w*h)n=w*h;
		for(int i=0;i<=n;i++)ans[i]=(i<=h);
		for(int k=2;k<=w;k++)
		{
			for(int i=k*h;i>=h+1;i--)ans[i]=(ans[i]-ans[i-h-1])%p;
			for(int i=1;i<=k*h;i++)ans[i]=(ans[i]+ans[i-1])%p;	
		}
		int s=-1-n/w;
		for(int i=0;i<=n;i++)s=(s+ans[i])%p;
		cout<<(s%p+p)%p<<endl;
	}
	return 0;
}

#include<iostream>
#include<string.h>
using namespace std;
 
int list[1001][1001];
int sum[1001];
 
int main()
{
	
	memset(list, 0, sizeof(list));
	memset(sum, 0, sizeof(sum));
	list[1][1] = 1;
	sum[1] = 1;
	for (int i = 2; i <= 1000; i++)for (int j = 1; j <= i; j++)
	{
		list[i][j] = (list[i - 1][j - 1] + list[i - 1][j])*j % 10056;
		sum[i] += list[i][j];
	}
	int t, n;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		cin >> n;
		cout << "Case " << i << ": " << sum[n] % 10056 << endl;
	}
	return 0;
}

class Solution {
public:
    int f(vector<vector<int>> &mat, int i, int j)
    {
        if (i < 0 || j < 0) return 0;
        if (i >= mat.size()) i = mat.size() - 1;
        if (j >= mat[0].size()) j = mat[0].size() - 1;
        return mat[i][j];
    }
    vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int K)
    {
        vector<vector<int>> s = mat, ans =mat;
        for (int i = 0; i < s.size(); i++) for (int j = 0; j < s[0].size(); j++) 
            s[i][j] = f(s, i - 1, j) + f(s, i, j - 1) - f(s, i - 1, j - 1) + mat[i][j];
        for (int i = 0; i < s.size(); i++) for (int j = 0; j < s[0].size(); j++)
            ans[i][j] = f(s, i + K, j + K) - f(s, i - K - 1, j + K) - f(s, i + K, j - K - 1) + f(s, i - K - 1, j - K - 1);
        return ans;
    }
};

const int p = 1000000007;
class Solution {
public:
	int dieSimulator(int n, vector<int>& rollMax) {
		rollMax.insert(rollMax.begin(), 0);
		long long ans[7][16], s[7] = { 0 };
		memset(ans, 0, sizeof(ans));
		for (int i = 1; i <= 6; i++)s[i] = ans[i][1] = 1, s[0] += s[i];
		while (--n)
		{
			for (int i = 1; i <= 6; i++)
			{
				ans[i][0] = ans[i][rollMax[i]];
				for (int j = rollMax[i]; j > 1; j--)ans[i][j] = ans[i][j - 1];
				ans[i][1] = s[0] - s[i];
			}
			s[0] = 0;
			for (int i = 1; i <= 6; i++)
			{
				s[i] = (s[i] + ans[i][1] - ans[i][0]) % p, s[0] += s[i];
			}
		}
		return (s[0]%p + p) % p;
	}
};

const int p = 1000000007;
class Solution {
public:
	int dieSimulator(int n, vector<int>& rollMax) {
		rollMax.insert(rollMax.begin(), 0);
		long long ans[7][16], s[7] = { 0 }, key[7];
		memset(ans, 0, sizeof(ans));
		for (int i = 1; i <= 6; i++)s[i] = ans[i][1] = 1, s[0] += s[i], key[i] = rollMax[i];
		while (--n)
		{			
			for (int i = 1; i <= 6; i++)
			{
				ans[i][0] = ans[i][key[i]], ans[i][key[i]] = s[0] - s[i];
				key[i] = (key[i] == 1) ? rollMax[i] : key[i]-1;
			}
			s[0] = 0;
			for (int i = 1; i <= 6; i++)
			{
				s[i] = (s[i] + ans[i][key[i] % rollMax[i] + 1] - ans[i][0]) % p, s[0] += s[i];
			}
		}
		return (s[0]%p + p) % p;
	}
};

#include<iostream>
#include<string.h>
using namespace std;

int num[31][31][51];

int f(int n, int m, int k)
{
	if (num[n][m][k]>-3000)return num[n][m][k];
	if (n*m == k)return 0;
	if (n*m < k)return -2000;
	if (k == 0)return 0;
	if (k < 0)return -2000;
	int s = 1000, t;
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= i*m && j <= k; j++)
		{
			t = f(i, m, j) + f(n - i, m, k - j) + m;
			if (t>=0 && s>t)s = t;
		}
	}
	for (int i = 1; i < m; i++)
	{
		for (int j = 0; j <= i*n && j <= k; j++)
		{
			t = f(n, i, j) + f(n, m - i, k - j) + n;
			if (t>=0 && s>t)s = t;
		}
	}
	num[n][m][k] = s;
	return s;
}

int main()
{
	for (int i = 0; i < 31; i++)for (int j = 0; j < 31; j++)
		for (int k = 0; k < 51; k++)num[i][j][k] = -3000;
	int t, n, m, k;
	cin >> t;
	while (t--)
	{
		cin >> n >> m >> k;
		cout << f(n, m, k) << endl;
	}
	return 0;
}

int p=1000000007;
long long res[51][101][51];
class Solution {
public:
    long long numOfArrays(int n, int m, int k) {
         if(n<=0||m<=0||k<=0||k>n||k>m)return 0;
         if(n==1)return m;
         if(m==1)return 1;
         if(res[n][m][k])return res[n][m][k];
         long long ans=numOfArrays(n,m-1,k)+(numOfArrays(n-1,m,k)-numOfArrays(n-1,m-1,k))*m%p+numOfArrays(n-1,m-1,k-1);
         return res[n][m][k] = (ans%p+p)%p;
    }
};

int maxint=1234567;
class Solution {
public:
    int ans[105][22][105];
    int dp(vector<int>& houses, vector<vector<int>>& cost, int m, int n,int nn, int target) {
        if(m==0)
        {
            if(target!=1)return maxint;
            if(houses[m]>0)return 0;
            return cost[0][nn-1];
        }
        if(target<=0)return maxint;
        if(ans[m][nn][target]<maxint)return ans[m][nn][target];
        if(houses[m]>0 && houses[m]!=nn)return maxint;
        for(int ni=1;ni<=n;ni++)ans[m][nn][target]=min(ans[m][nn][target],((houses[m]>0)?0:cost[m][nn-1])+dp(houses,cost,m-1,n,ni,target-(ni!=nn)));
        return ans[m][nn][target];
    }
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        for(int i=0;i<=m;i++)for(int j=0;j<=n;j++)for(int k=0;k<=target;k++)ans[i][j][k]=maxint;
        int r=maxint;
        for(int ni=1;ni<=n;ni++)r=min(r,dp(houses,cost,m-1,n,ni,target));
        if(r==maxint)return -1;
        return r;
    }
};

int maxint=1234567;
class Solution {
public:
    int ans[105][22][105];
    int dp(vector<int>& houses, vector<vector<int>>& cost, int m, int n,int nn, int target) {
        if(m==0)
        {
            if(target!=1)return maxint;
            if(houses[m]>0 && houses[m]!=nn)return maxint;  add
            if(houses[m]>0)return 0;
            return cost[0][nn-1];
        }
        if(target<=0)return maxint;
        if(ans[m][nn][target]<maxint)return ans[m][nn][target];
        if(houses[m]>0 && houses[m]!=nn)return maxint;
        ans[m][nn][target]--;
        for(int ni=1;ni<=n;ni++)ans[m][nn][target]=min(ans[m][nn][target],((houses[m]>0)?0:cost[m][nn-1])+dp(houses,cost,m-1,n,ni,target-(ni!=nn)));
        return ans[m][nn][target];
    }
    int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
        for(int i=0;i<=m;i++)for(int j=0;j<=n;j++)for(int k=0;k<=target;k++)ans[i][j][k]=maxint;
        int r=maxint;
        for(int ni=1;ni<=n;ni++)r=min(r,dp(houses,cost,m-1,n,ni,target));
        if(r>maxint-2)return -1;
        return r;
    }
};