题意
给定若干线段，每条线段可以覆盖一个连续整数区间，需要付出一定代价，问至少覆盖k个整数最少需要付出多少代价
思路
区间dp，在读入线段的时候，对连续一段区间的代价进行记录与更新，然后做区间dp，dp[i][j]表示到i为止覆盖j个区间需要付出的最小代价，dp[i][j]=max(dp[i][j],dp[i][k]+a[i-k+1][i])，a数组就是提前处理出的连续区间的代价，最后dp[n][k]就是答案
代码
#include <cstdio>
#define INF 1000000000000000000LL
long long co[
301][
301],ans[
301][
301];
int main()
{
long long n,m,k,l,r,c;
scanf(
"%I64d%I64d%I64d",&n,&m,&k);
for(
long long i=
0;i<=n;i++)
for(
long long j=
1;j<=n;j++)
{
co[i][j]=INF;
ans[i][j]=INF;
}
for(
long long i=
0;i<m;i++)
{
scanf(
"%I64d%I64d%I64d",&l,&r,&c);
for(
long long j=l;j<=r;j++)
if(co[l][j]>c)
co[l][j]=c;
}
for(
long long i=
1;i<=n;i++)
for(
long long j=
1;j<=k&&j<=i;j++)
{
ans[i][j]=ans[i-
1][j];
for(
long long kk=
1;kk<=j;kk++)
if(ans[i][j]>ans[i-kk][j-kk]+co[i-kk+
1][i])
ans[i][j]=ans[i-kk][j-kk]+co[i-kk+
1][i];
}
if(ans[n][k]!=INF)
printf(
"%I64d\n",ans[n][k]);
else printf(
"-1\n");
return 0;
}
