Topcoder 2015_1C

A:大水题;

B:求一颗树中，有多少条路径 不存在路径中一点是另外一点的祖先，（后面废话说了很多）

其实一个点 可以到它本身也可以是一条路径结论是：统计叶子的节点。（真简单粗暴

C:题目不说，说也说不好 23333

思路：当前枚举到i,枚举i之前的k 然后看 k+1到 i 组成的美丽度 是多少，

统计方法是在枚举一维 j<=cnt;上判断：

具体方程： tmp=(i-k)*(i-k+1)/2;

               dp[i][j]+=dp[k][j-tmp];(j>=tmp);

 初始化 dp[0][0]=2;因为之前 位数为1时，就可以为2.（这里解释有点问题，其实是这样的，开始为2,其实答案一定是偶数，还是很抽象，

                                                                                    举个例子，010->101,这两个（beauty)是一样的，不过是相同位反过来，所以这份代码，由初始直搞定，后续中并没有严格分开来。）不过转移方程 的确很神奇

代码： 

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string.h>
#include<string>
#include<iostream>
#include<vector>
#include<map>
#include<vector>

#define N 123456
#define inf 0x3f3f3f
using namespace std;
typedef long long ll;

ll dp[55][2555];
class DevuAndBeautifulSubstrings
{
    public:
    long long countBeautifulSubstrings(int n, int cnt)
    {
        dp[0][0]=2;
        for (int i=1;i<=n;i++)
        for (int j=1;j<=cnt;j++)
        {
            for (int k=0;k<i;k++)
            {
                int tmp=(i-k)*(i-k+1)/2;
                if (j>=tmp) dp[i][j]+=dp[k][j-tmp];
            }
        }
        return dp[n][cnt];
    }
};


int main()
{
    int n,cnt;
    cin>>n>>cnt;
    DevuAndBeautifulSubstrings p;
    cout<<p.countBeautifulSubstrings(n,cnt)<<endl;
    return  0;
}