[数据结构与算法]CF 1625C. Road Optimization（DP）

Linking

题意：

在一条直线道路从A到走向B点，A点位于0位置，B点位于m位置。
道路上有n个时速牌，第i个牌上标有ai，表示从该时速牌到下一时速牌这段距离中，每走一个位置耗时ai分钟。（初始位置0上有时速牌）
现在要移除k个时速牌（0位置不可移），问移除之后从A到B的时间最少为多少？

思路：

状态表示：
dp[i,j]：删除j个标志，到前i+1个位置所用的最少时间。
状态转移：

• 当前位置的标志不删除：
  上一位置的删除j个的状态加上当前这段距离所需要的时间：dp[i][j] = dp[i-1][j] + a[i]*(b[i+1]-b[i]);
• 当前位置的标志删除：
  需遍历前面所有状态以求得最优解：
  遍历上一个标志所在的位置，中间的所有标志都要删除，那么上一个位置的状态就为 dp[s][j-(i-s)] ，加上该标志位置到当前位置这段路程所需要的时间。

for(int s=1;s<i;s++) 
{
	dp[i][j] = min(dp[i][j], dp[s][j-(i-s)]+a[s]*(b[i+1]-b[s+1]));
}

Code：

const int N = 2010, mod = 1e9+7;
int T, n, m, k;
int a[N], b[N], dp[N][N];

signed main(){
	cin>>n>>m>>k;
	
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	
//	dp[i][j]：删除j个标志，到前i+1个位置的最少时间。 
	mem(dp,0x3f);
	dp[0][0] = 0;
	b[n+1]=m, a[0]=1e18;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i,j<=k;j++)
		{
			dp[i][j] = dp[i-1][j] + a[i]*(b[i+1]-b[i]); //当前位置的标志不删除 
			
			for(int s=1;s<i;s++) //当前标志删除，从前面的所有位置转移状态。 
			{
				dp[i][j] = min(dp[i][j], dp[s][j-(i-s)]+a[s]*(b[i+1]-b[s+1]));
			}
		}
	}
	
	int ans=1e18;
	for(int i=0;i<=k;i++) ans=min(ans, dp[n][i]);
	cout<<ans;
	
	return 0;
}