At dp综合

感觉整体比较板，但还是挺有质量的）

A Frog 1（直接dp）

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],f[100005];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",a+i),f[i]=1e9;
	f[1]=0;f[0]=1e9;
	for(int i=2;i<=n;i++) f[i]=min(f[i-1]+abs(a[i-1]-a[i]),f[i-2]+abs(a[i]-a[i-2]));
	cout<<f[n];
	return 0;
}

B Frog 2（直接dp）

        数据范围完全可以直接nk做

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],f[100005];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",a+i),f[i]=1e9;
	f[1]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=min(i-1,m);j++)
			f[i]=min(f[i],f[i-j]+abs(a[i]-a[i-j]));
	cout<<f[n];
	return 0;
}

C Vacation（直接dp）

        简单分类讨论一下即可

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,a[N],b[N],c[N],f[N][4];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",a+i,b+i,c+i);
	for(int i=1;i<=n;i++)
		f[i][1]=max(f[i-1][2],f[i-1][3])+a[i],
		f[i][2]=max(f[i-1][1],f[i-1][3])+b[i],
		f[i][3]=max(f[i-1][1],f[i-1][2])+c[i];
	cout<<max(max(f[n][1],f[n][2]),f[n][3]);
	return 0;
}

D Knapsack 1（01背包）

        纯板子     

#include<bits/stdc++.h>
using namespace std;
long long n,W,w,u,ans,f[100005];
int main()
{
	scanf("%lld%lld",&n,&W);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&w,&u);
		for(int j=W;j>=w;j--) f[j]=m