漫游浏览

同长条大街被分成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;
}