P1 祖玛

区间DP，我们定义f(l,r)为最少的缩减次数，那么

1如果s[l]==s[r]，那么直接等价于求解f(l+1,r-1)

2如果不相等，直接枚举k进行划分，f(l,k)+f(k+1,r)里面的最小值即可。

主要代码如下：

int get(int l, int r) {
    if (l == r) return 1;
    if (dp[l][r]) return dp[l][r];
    dp[l][r] = inf;
    for (int i = l; i < r; i++) 
        dp[l][r] = min(dp[l][r], get(l, i) + get(i + 1, r));

    if (s[l] == s[r]) dp[l][r] = min(dp[l][r], get(l + 1, r - 1));
    return dp[l][r];
}

P2团队竞赛

先sort，让数据有序化！！

假设三个选手是a，b，c，那么我们枚举a，然后二分或者尺取b和c的范围k，记得利用组合数C(k,2)就是a的组合情况，继续循环枚举即可！

	for(int i=1;i<=n;i++)
	{
		if(a[i]+m==a[n])
		{
			ans+=C(n-i,2ll);
			continue;
		}
		int x=upper_bound(a+1,a+n+1,a[i]+m)-a;
		int t=x-1-i;
		ans+=C(t,2ll);
	}

P3整数划分

30分做法就是dfs穷举

我们考虑利用背包进行计数，那么我们可以得到， dp[j]=(dp[j]+dp[j-i])%1000000007;的递推式，那么我们可以枚举所有的i即可！

P4遇到麻烦

其实和P3差不多，我们考虑利用dp枚举所有的组合方案，由于砝码可以放在左边，那么预处理给砝码留一份负数的！

	for (int i = 1; i <= n; i ++)
		for (int j = sum; j >= 0; j --){
			dp[i][j] = dp[i - 1][j];
			if (a[i] == j) dp[i][j] = 1;
			if (dp[i - 1][j + a[i]] == 1) dp[i][j] = 1;
			if (dp[i - 1][abs(j - a[i])] == 1) dp[i][j] = 1;
		}

P5打字

bfs或者DP都可以！

P6粉刷匠

状态dp，DP[i][j]，我们用i表示处理到i个房子，j表示刷的颜色，所以我们开两个维度即可，主要就是这么转移，由于相邻房子不能颜色相同，那么不同颜色直接转移即可！

    dp[i][0]=min(dp[i-1][1],dp[i-1][2])+a[i][0];
    dp[i][1]=min(dp[i-1][0],dp[i-1][2])+a[i][1];
    dp[i][2]=min(dp[i-1][1],dp[i-1][0])+a[i][2];