1、奶牛零食

https://www.acwing.com/problem/content/4561/
题意：给我们一个序列，我们可以从前面拿一个数，也可以从后面拿一个数，然后每拿一个数都会有一个值，这个值是$i\ast a[i]$，然后问我们最大值是多少。

思路 ：首先我们进行状态表示f[i][j表示的是我们在前面取i个数和在后面取j个数的权值最大是多少。属性就是Max。然后我们把集合划分为两个部分，一个是最后一次弹出的是i，另一个则是最后一个弹出的是j。那么状态转移方程就是$$f[i][j]=max(f[i-1][j]+(i+j)\ast a[i],f[i][j-1]+(i+j)\ast b[j])$$

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2010;
int a[N];
int b[N];
long long f[N][N];

int main()
{
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int n;
     cin >> n;
     for (int i = 1; i <= n; i++)
     {
          cin >> a[i];        //我们读入a[i]
          b[n - i + 1] = a[i];//我们倒着进行b[]数组的额记录
     }

     for (int i = 1; i <= n; i++)//首先我们要考虑特殊的情况，这个按照我们集合的表示就是一直从前面选
          f[i][0] = f[i - 1][0] + i * a[i];
     for (int i = 1; i <= n; i++)//这个就是我们一直从后面选
          f[0][i] = f[0][i - 1] + i * b[i];

     for (int i = 1; i <= n; i++)//由于我们在上面已经判断过0的情况了，所以我们就直接从1开始
     {
          for (int j = 1; j <= n - i; j++)//i+j的和不能超过n
          {
               //我们正常的转态转移方程
               f[i][j] = max(f[i - 1][j] + (i + j) * a[i], f[i][j - 1] + (i + j) * b[j]);
          }
     }
     long long res = 0;
     for (int i = 0; i <= n; i++)
     {
          res = max(res, f[i][n - i]);
     }
     cout << res << endl;
     return 0;
}

2、免费陷阱

题意：现在给我们一个从0到10的数轴，然后每一秒钟都会有一些馅饼掉在这个数轴上，在每一秒钟一个点只能掉下来一个馅饼。然后我们一开始在5的位置，我们一次可以接相邻两个点的馅饼，然后我们每秒钟可以向左或者向右移动一个单位。问我们最多可以接到多少个馅饼。
思路：其实这个题比较不好看，但是同过分析我们可以看到它其实是一个数字三角形的变形，只不过我们这里以相邻的三个点作为一个点类似这样的一个图

然后我们就可以进行状态表示，f[i][j]表示的是我们从第i秒到走到下标是j的地方我们可以拿到到少馅饼，属性就是Max。状态的计算就是$$f[i][i]=max(f[i+1][j],max(f[i+1][j-1],f[i+1][j+1]))$$
然后我们就可以写出代码

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100001;
int f[N][20];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	while (cin >> n)
	{
		if (n == 0)
			break;
		int t = -1;
		memset(f, 0, sizeof f);
		for (int i = 0; i < n; i++)
		{
			int x, y;
			cin >> x >> y;
			f[y][x]++;//我们一边读入一边记录
			if (y > t)
				t = y;//看我们最长的时间是多少
		}
		for (int i = t; i >= 0; i--)//从我们的第t秒倒着找。
		{
			for (int j = 10; j >= 0; j--)
			{
				f[i][j] = max(f[i + 1][j], max(f[i + 1][j - 1], f[i + 1][j + 1])) + f[i][j];
			}
		}
		cout << f[0][5] << endl;
	}
	return 0;
}

3、猪猪存钱罐

思路：首先这个题我们通过分析的话，可以得出我们其实要求的是一个，完全背包的问题，但是我们完全背包的状态表示要变一下。此时的f[i][j]表示的是我们从前i个物品中选，然后重量恰好等于j的最小价值是多少，然后它的属性就是Min。下面我们来看状态计算，我们可以按照完全背包一样的划分就可以。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6 + 10;
int v[N];
int w[N];
int f[N];

void solve()
{
	int E,F;
	cin>>E>>F;
	int V = F - E;
	int n;
	cin>>n;
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=v[i];j<=V;j++)
		{
			f[j]=min(f[j],f[j-v[i]]+w[i]);	
		}
	}
	if(f[V]==0x3f3f3f3f)
		cout<<"This is impossible."<<'\n';
	else
		cout<<"The minimum amount of money in the piggy-bank is "<<f[V]<<'.'<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}