觀光浏覽,觀光浏覽車
一條街道被分成m格(1<=m<=100),還有n個景點(1<=n<=100),分布在街道上。每個景點可以占據連續的若干格,並且有一個美學值v(0<v<=100)。現要組織k個人考察這個街道(1<=k<=m),每個人考察的區域是連續的若干格(不可為0格),且任意兩個人考察的區域不得相交,也不得有一個格子無人考察。對於任意一個人,如果它考察的區域中有一個風景點(風景點必須完整的位於這個區域),則它就得到了這個風景點的分值(美學值)。
你的任務是將街道的m個格子分給k個人去考察,使得總的分值最大。
【輸入文件】
第一行一個整數m,表示街道的長度。
第二行一個整數n,表示風景點個數。
此後n行,每行描述一個風景點,三個整數x、y和v,表示該風景點是從第x個格子到第y個格子,美學值為v。
最後一行一個整數k,表示考察的人數。
【輸出文件】
一個整數,表示最大可以得到的分值。
【輸入輸出樣例】
輸入:
3
2
1 2 2
2 3 3
2
輸出:
3
【參考程序】:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int f[101][101],c[101][101];
int n,m,k;
int main()
{
freopen("view.in","r",stdin);
freopen("view.out","w",stdout);
scanf("%d",&n);scanf("%d",&m);
memset(c,0,sizeof(c));
int x,y,v;
for (int t=1;t<=m;t++)
{
scanf("%d%d%d",&x,&y,&v);
for (int i=1;i<=x;i++)
for (int j=y;j<=n;j++)
c[i][j]+=v;
}
scanf("%d",&k);
memset(f,128,sizeof(f));
f[0][0]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
for (int l=0;l<=i-1;l++)
if (f[i][j]<f[l][j-1]+c[l+1][i])
f[i][j]=f[l][j-1]+c[l+1][i];
printf("%d\n",f[n][k]);
return 0;
}