信息学奥赛一本通T1262：动态规划的基本模型 挖地雷

【题目描述】在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向在序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。【输入】第一行：地窖的个数

信息学奥赛一本通T1262：挖地雷

【题目描述】

在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向在序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。

【输入】

第一行：地窖的个数；

第二行为依次每个地窖地雷的个数；

下面若干行：

xi yi  //表示从xi可到yi，xi<yi。

最后一行为"0 0"表示结束。

【输出】

k1−k2−…−kv   //挖地雷的顺序
挖到最多的雷。

【输入样例】

6
5 10 20 5 4 5
1 2
1 4
2 4
3 4
4 5
4 6
5 6
0 0

【输出样例】

3-4-5-6
34

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 201
#define MOD 2520
#define E 1e-12
using namespace std;
int g[N][N];
int w[N],pre[N];
int f[N];
void print(int k)
{
    if(k==0)
        return;

    print(pre[k]);

    if(pre[k]==0)
        cout<<k;
    else
        cout<<"-"<<k;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        f[i]=w[i];
    }

    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF&&x&&y)
        g[x][y]=1;

    int maxx=-INF,k;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if( g[j][i]==1 && f[j]+w[i]>f[i] )
            {
                f[i]=f[j]+w[i];
                pre[i]=j;
            }
        }
        if(f[i]>maxx)
        {
            maxx=f[i];
            k=i;
        }
    }
    print(k);
    cout<<endl<<maxx<<endl;
    return 0;
}

 

信息学奥赛一本通T1262：动态规划的基本模型 挖地雷 归属于 动态规划的基本模型，更多同类题解源程序见：动态规划的基本模型 和 挖地雷

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！