[数据结构与算法]Codeforces Round #765 (Div. 2)C. Road Optimization---DP

状态表示：f[i][j] 表示 前i个站点，移走 j个车牌的最小权值
状态转移：

车牌可以连续移走也可以单个移走，我们枚举小于i的所有站点j,拿走j到i之间所有的车牌，可以实现状态的全覆盖，需要判断可拿走车牌的数量k要大于i-j-1

状态转移方程：f[i][k]=min(f[i][k],f[j][k-(i-j-1)]+v[j]*(d[i]-d[j]))

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n,l,m;
int d[N],v[N];
int f[N][N];//f[i][j]  表示  前i个站点，移走 j个车牌的最小权值 
signed main()
{
    memset(f,0x3f,sizeof f);
	cin>>n>>l>>m;
    for(int i=1;i<=n;i++)cin>>d[i];
    for(int i=1;i<=n;i++)cin>>v[i];
    n++,d[n]=l;
    for(int i=0;i<=m;i++)f[1][i]=0;
    for(int i=2;i<=n;i++)
    {
    	for(int j=1;j<i;j++)
    	{
    		for(int k=i-j-1;k<=m;k++)
    		{
    		    f[i][k]=min(f[i][k],f[j][k-(i-j-1)]+v[j]*(d[i]-d[j]));
			}
		}
	}
	cout<<f[n][m]<<endl;
}