动态规划

题目练习

开餐馆

#include<bits/stdc++.h>
using namespace std;
struct point
{
	int val;
	int p;
};
int t,n,m;
int sss[1010] = {0};
int sl=0;
int main()
{
	cin>>t;
	while(t--)
	{
		point a[1010] = {0};
		int dp[1010] = {0};
		cin>>n>>m;
		for(int i = 1;i<=n;i++)
		{
			cin>>a[i].p;
		}
		for(int i = 1;i<=n;i++)
		{
			cin>>a[i].val;
		}
		dp[1] = a[1].val;
		for(int i = 2;i<=n;i++)
		{
			dp[i] = dp[i-1];
			for(int j = i-1;j>=1;j--)
			{
				if(a[i].p-a[j].p>m)
				{
					dp[i ] =dp[j]+a[i].val;
					break;
				}
			}
		}
		sss[sl] = dp[n];
		sl++;
	}
	for(int i = 0;i<sl;i++)
	{
		cout<<sss[i]<<endl;
	}
	return 0;
}

吃奶酪

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int a[100010] = {0};
		for(int i = 0;i<n;i++)
		{
			cin>>a[i];
		}
		int dp[100010] ={0};
		dp[0] = a[0];
		dp[1] = max(a[0],a[1]);
		for(int i = 2;i<n;i++)
		{
			dp[i] = max(dp[i-2]+a[i],dp[i-1]);
		}
		cout<<dp[n-1]<<endl;
	}
	return 0;
}