程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 觀光浏覽,觀光浏覽車

觀光浏覽,觀光浏覽車

編輯:C++入門知識

觀光浏覽,觀光浏覽車


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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved