ps: 自己的方法绝对是弱爆了
肯定存在更优的方法
O(n^3)复杂度 暴力求解的。。
链接：https://www.nowcoder.com/acm/contest/121/K
来源：牛客网
柯怡最近开始沉迷赌博，比如跟别人赌这次陕西皇家女子学院举办的校赛里面，AK人数的奇偶；
而这种赌博显然柯怡稳赚不赔，因为她可以偷偷参加校赛，然后在最后一分钟观察AK的人数，如果她赌的是奇数而那时有偶数个人AK，她只要用这剩下的一分钟自己AK一次就可以让数量变回偶数了；
聪明的ddjing发现了老千柯怡的阴险套路，万般无奈的柯怡只好更改赌博的套路，这次她觉得跟ddjing玩猜数字；
这个游戏很简单，规则是，柯怡和ddjing在游戏开始前，先规定数字的范围是1到n，而柯怡则从这n个数里面选出一个x并默默记在心中，每次ddjing去猜一个数y，柯怡会告诉ddjing，他是猜大了（y>x）还是猜小了（y<x），亦或者是猜对了（y==x）；
而赌注则是，每次ddjing去猜一个数y的时候，若他没有猜中，那么他就需要向柯怡赠送y套女装（因为这是柯怡的最爱），如果他猜中了，那柯怡将会穿着小裙裙来到比赛现场给大家发气球；
虽然柯怡允许每次游戏的时候，ddjing可以猜任意次，直到猜中为止，但这显然可以为柯怡提供出千的可能，比如说，柯怡心中所选之数是x，而ddjing第一次就猜中了，然后柯怡就会马上变更她心中所选之数为x，同时告诉ddjing他猜大了还是猜小了，但柯怡不会破坏游戏规则（比如说ddjing猜了5，柯怡告诉ddjing猜大了，那新的数就不能是小于等于5的数）；
虽然ddjing知道这个游戏有很大的出千空间，但他知道，只要付出足够多的女装，就能稳定赢得最后的胜利；
但ddjing手头比较紧，他想知道，对于猜测1~n的游戏，在柯怡不断出千的情况下，他最少要准备多少套女装，才能保证一定能猜到最终结果；
输入描述:
第一行一个整数T（T<=100），代表数据组数；
对于每组数据，只有一行整数n（n<=300），代表游戏的数字范围；
输出描述:
对于每组数据，输出一个整数，代表ddjing至少需要准备的女装数目；
输入例子:
3
1
2
3
输出例子:
0
1
2
-->
输入
3
1
2
3
输出
0
1
2
说明
当n=1时，ddjing只要猜1就能猜中，所以不用赠送女装；
当n=2时，ddjing柯怡猜1，下一次就肯定能猜中，所以只需要赠送一件女装就好；
当n=3时，ddjing只要猜2，下一次就肯定能猜中，只需要要赠送两件女装就好；
#include <bits/stdc++.h>
using namespace std;
const int N=;
const int INF=0x3f3f3f3f;
int dp[N][N];
int main ()
{
for (int l=;l<=;l++)
for (int i=;i+l<=;i++) {
int j=i+l-;
dp[i][j]=INF;
for (int k=i;k<=j;k++) {
int t1=,t2=;
if (k!=i) t1=dp[i][k-];
if (k!=j) t2=dp[k+][j];
int tmp=max (t1,t2)+k;
dp[i][j]=min (dp[i][j],tmp);
}
}
int T; scanf ("%d",&T);
while (T--) {
int n; scanf ("%d",&n);
printf("%d\n",dp[][n]);
}
return ;
}