Road Optimization

呃，我是第一次参加这个div2，我一小时做完前三道就留了，三发全中，写个题解说一下我的C题思路，A,B题没啥好说的。
C题是一个简单的dp，我们定义状态量为dp[i][j] ，表示从最后一块牌子到第i块牌子删了j次所需要的最小花费 ， 我从后往前枚举，因为第一块牌是一定不能删掉的。所以答案是max(dp[1][j]) j <-[0 , k] 。
然后开始枚举状态。
状态转移为
dp[i][j] = min(dp[i + p][j - (p - 1)]) p <- (1 - n)
就是i不拆，到j不拆，（i - j)之间的都拆了的最小花费。
不说了看代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
 
using namespace std ;
 
const int N = 500 + 10 ;
const int Inf = 0x3f3f3f3f ;
 
int f[N][N] ;
int d[N] , a[N] ;
 
int main(void)
{
	int n , l , k ;
	scanf("%d%d%d" , &n , &l , &k) ;
	for(int i = 1 ; i <= n ; i ++) scanf("%d" , &d[i]) ;
	for(int i = 1 ; i <= n ; i ++) scanf("%d" , &a[i]) ;
	d[n + 1] = l ;
	memset(f , 0x3f , sizeof f) ;
	f[n + 1][0] = 0 ;
	for(int i = n ; i >= 1 ; i --)
	{
		for(int j = 0 ; j <= k ; j ++)
			for(int z = i + 1 ; z <= n + 1 && j - (z - i - 1) >= 0 ; z ++)
				f[i][j] = min(f[i][j] , f[z][j - (z - i - 1)] + (d[z] - d[i]) * a[i]) ;
	}	
	int ans = Inf ;
	for(int i = 0 ; i <= k ; i ++)
		ans = min(f[1][i] , ans) ;
	printf("%d" , ans) ;
}

纪念第一次参加div2三发就跑。溜~~~~