T1牛奶供应

考察的是队列，那我们把内容放入队列，过期的就出队，没过期的就统计，统计的时候考虑能不能收购！

	while (r <= n) {
		if (r-l > m) l++;
		while (l<=r && c[r]!=0) {
			if (p[l] <= c[r]) {
				sum += p[l];
				c[r] -= p[l];
				l++;
			} else {
				sum += c[r];
				p[l] -= c[r];
				c[r] = 0;
			}
		}
		r++;
	}

T2算24

考察内容为dfs，设计dfs的时候，要考虑放下的符号有优先级，当然，可以利用栈对表达式进行计算。

这里利用dfs枚举出符号，然后利用堆栈进行计算！

bool cal()
{
	stack<int>num;
	stack<int>op;
	num.push(a[1]);
	for(int i=2;i<=n;i++)
		if(t[i]==3)
		{
			int s=num.top()*a[i];
			num.pop();
			num.push(s);
		}
		else num.push(a[i]),op.push(t[i]);
	while(!op.empty())
	{
		int y=num.top();num.pop();
		int x=num.top();num.pop();
		int z=op.top();op.pop();
		if(z==1) num.push(x+y);
		else num.push(x-y);
	}
	if(num.top()==24) return true;
	else return false;
}

T3货币系统

考察DP，完全背包，具体转移看解释

  f[0]=1;//上面是面值，f[i]表示面值为i时方案数，0初始为1，因为唯一的方案就是不放钱
  for(int i=1; i<=v; ++i) //枚举每种面值
    for(int j=p[i]; j<=n; ++j) //这也是完全背包写法，可无限用，如果j<该面值无需枚举，如果j>总数不合题意了（浪费时间）
      f[j]=(f[j]+f[j-p[i]])%mod;//因为从前往后，更新j面值时的方案数

T4观光车

因为每个观光车只能坐两个人，所以考虑一个策略，就是排序后，左右指针枚举，算法时间复杂度O(N)

考察 sort+双指针

    sort(a + 1, a + n + 1);//排序
    int left = 1;//左指针指向最轻的人
    int right = n;//右指针指向最重的人
    while (left < right) {//直到指针重合
        if (a[left] + a[right] <= t) {//如果可以配对
            ans++;//用一辆车
            left++;//左加
            right--;//右减
        } else {//如果不能配对
            ans++;//给体重重的单独配一辆车
            right--;//右减
        }
    }    if (right == left) ans++;//如果最后剩一个人，单独用一辆车

T5回文游戏

区间DP，考虑i和j相等的时候，直接由dp[i+1][j-1]转移过来呢？如果不相等，考虑DP[i][j-1]或者DP[i+1][j]更优解而来

	for(int len = 2; len <= n; len++){
		for(int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			//必须要有j - i > 1，因为j - i == 1这种情况在初始化已经被更新了，且是最优值
			//为什么当相等的时候，直接由dp[i+1][j-1]转移过来呢？
			//因为区间[i+1,j-1]合并到最后会剩下一个回文串，回文串两端加上相同的字母还是回文串，合并次数不变 
			if(a[i] == a[j] && j - i > 1) {
				dp[i][j] = dp[i + 1][j - 1];
			}
			for(int k = i; k < j; k++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
		}
	}

T6多边形划分

区间DP，考虑2条边是没办法构成三角形的，所有初始化为0，三条边的时候，利用k进行划分，dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + i * k * j);

	for(int len = 2; len <= n; len++){
		for(int i = 1; i + len - 1 <= n; i++){
			int j = i + len - 1;
			for(int k = i; k < j; k++){//其他题目区间是不包含关系，所以是k+1
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + i * k * j);
			}
		}
	}