观光浏览

2018-06-17 23:51:05来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

一条街道被分成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;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:快速幂+大数取模

下一篇:【NOIP训练】【数论】超级计算机