AcWing 1011. 挖地雷    原题链接    简单

作者： 作者的头像   Pr ,  2020-04-30 16:19:35 ,  所有人可见 ,  阅读 959

5


1

算法分析：

同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向大序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。
上述题意告诉我们该图是个拓扑图，可按照递推的顺序来解决

思路：动态规划：

f[i]表示所有以i为终点的扫雷的最大数量，f[i]=f[j]+w[i],j满足g[j][i]=1,由于是拓扑图，可以写for循环
pre[i]记录i点是由哪个点转移过来的，便于求轨迹；

#include<bits/stdc++.h>
using namespace std;
const int N=210,INF=0x3f3f3f3f;
int g[N][N], w[N],pre[N];//pre数组存储当前状态由哪一个转移过来
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++)
    { scanf("%d",&w[i]);
      f[i]=w[i];//f数组储存在i点的max,表示的集合，发f(i)=max(f(j)+w[i],f[i]),且给g[j][i]==1 
    }
    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[i]<f[j]+w[i])
          {
              f[i]=f[j]+w[i];
              pre[i]=j;//表示发f(i)由f(j)转移过来
          }
      }
       if(f[i]>maxx)
       {
           maxx=f[i];
           k=i;//k用来标记最后挖地雷停止的标记点
       }
    }
   cout<<endl<<maxx<<endl;
   return 0;
}

4 评论

用户头像
天命   2020-04-30 16:44         踩      回复

你的格式崩了啊喂 /笑哭

用户头像
Pr   2020-04-30 18:29         踩      回复

第一次写这个hh

用户头像
3k   2022-02-27 10:16    回复了 Pr 的评论         踩      回复 
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 205;
int n,a[N],s[N][N],ans = 0,pre[N];
int x,y;
int f[N],flag = 0;
void print(int x)
{
    if(pre[x] == 0) 
    {
        printf("%d",x);
        return;
    }
    print(pre[x]);
    printf("-%d",x);
}
int main()
{
    freopen("mine.in","r",stdin);
    freopen("mine.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    while(scanf("%d %d",&x,&y))
    {
        if(x == 0 && y == 0) break;
        s[x][y] = 1;
    }
    for(int i = 1;i <= n;i ++)
    {
        f[i] = a[i];
        for(int j = 1;j < i;j ++)
        {
            if(s[j][i] == 1)
            {
                if(f[j]+a[i] > f[i])
                {
                    f[i] = f[j]+a[i];
                    pre[i] = j;
                }
            } 
        }
        if(f[i] > ans)
        {
            ans = f[i];
            flag = i;
        }
    }
    print(flag);
    printf("\n%d\n",ans);
    return 0;
} 
/*
输入样例： 
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 
*/
用户头像
Pr   2020-04-30 16:19         踩      回复

hh