一、取数游戏
双人游戏，N（2<=N<=100)个正整数序列放在一个桌子上，两人轮流从序列的两端的任意一端取数。
Alice 和Bob 轮流取数，Alice先取，两人都足够聪明，问最后两人的最高的得分是多少？
思路：s[M][M]保存先手先拿和后拿能取得的最优值；
如果先拿，可以取这个数，而且是拿左边、拿右边两者中最优的一个。
如果后拿，对方回拿左边和拿右边两者中最优的一个，那么自然留下来的就最少！
#define M 105
int a[M],n;
int s[M][M];
int dfs(int l,int r,int who)
{
if(s[l][r])return s[l][r];
if(l==r&&!who){s[l][r]=a[l];return a[l];}
if(l==r&& who){s[l][r]=0;return 0;}
//先拿
if(!who) return s[l][r]=max(dfs(l+1,r,!who)+a[l],dfs(l,r-1,!who)+a[r]);
else return s[l][r]=min(dfs(l+1,r,!who),dfs(l,r-1,!who));
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
scanf("%d",a+i);
CLS(s,0);
int ans=dfs(0,n-1,0);
printf("%d %d\n",ans,accumulate(a,a+n,-ans));
}
return 0;
}二、签到积分
Description
经过一段时期的观察，老师觉得ACM实验室的利用率太低了，于是决定雇用老套的签到积分制度，但考虑到ACMer的成长必须持之以恒，因此，专门设计了一种激励连续签到的规则。
签到积分规则如下：
1） 每天只要来到ACM实验室学习并录入指纹，即算签到成功，可获取相应的积分；若某天未签到，则当天计0个积分。
2） 连续签到时，第1天签到可获取1个积分，第2天签到可获取2个积分，……，第n天可获取n个积分。
3） 如果中途未签到，则再签到时，连续天数重新从1开始计算。
自从有了积分制度后，ACM实验室的利用率大大的提高。
有一天集训队队长在签到后向大家出了一个难题，她向大家亮出了自己的签到积分总和，然后要大家算出她至少要签到多少天，并算出从开始签到到最后签到之间至少有多少天未签到。
Input
有多组测试数据
每行输入1个一个正整数n（1<=n<=170000）
Output
与输入的测试数据相对应，每行输出2个数据，一个是签到的最少天数，一个是中途未签到的最少天数，2个数用空格隔开。
思路：有600件商品,体积为v[i],每件花费为i,用最少的花费装满背包（=最少签到天数）
体积为v[i],每件花费为1,用最少的花费装满背包（=中途未签到的最少天数+1）
每件物品无数多件，那就是一个完全背包问题（上面所求的两个子问题没有依赖关系）
如果有依赖关系，比如：n=33，33=28+3+1+1 最少签到天数是11(7+2+1+1)，中途未签到最少次数为3,
33=21 +6+6 最少签到天数是12 (6+3+3)，中途未签到最少次数为2。
#define M 170005
int v[600]= {0};
int day[M]= {0},cost[M]= {0};
void init()
{
for(int i=1; i<600; i++) v[i]=v[i-1]+i;
for(int i=1; i<M; i++) day[i]=cost[i]=INF;
for(int i=1; i<600; i++)
for(int j=v[i]; j<M; j++)
{
day[j]=min(day[j-v[i]]+i,day[j]);
cost[j]=min(cost[j-v[i]]+1,cost[j]);
}
}
int main()
{
init();int n;
while(~scanf("%d",&n))
{
printf("%d %d\n",day[n],cost[n]-1);
}
return 0;
}