【NOIP2018】 摆渡车

题目：摆渡车

解题思路：

NOIP2018 PJ T3

时隔一年还是会感到有一些难度，让我措手不及，所以我这次做出来了，虽然不是自己做的，但是明白了意思，在基础上又进步了一大步

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,t[505],mem[505][505];
int solve(int i,int st)
{
	if(i==n+1)
	return 0;
	if(st<t[i])
	return solve(i,t[i]);
	if(mem[i][st-t[i]])
	return mem[i][st-t[i]];
	int sum=0,j=i;
	while(j<=n&&t[j]<=st)
	sum+=t[j++];
	int best=st*(j-i)-sum+solve(j,st+m);
	for(;j<=n;j++)
	{
		sum+=t[j];
		best=min(t[j]*(j-i+1)-sum+solve(j+1,t[j]+m),best);
	}
	return mem[i][st-t[i]]=best;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>t[i];
	sort(t+1,t+n+1);
	cout<<solve(1,0)<<endl;
	return 0;
}