1.挖地雷

题目背景

NOIp1996提高组第三题

题目描述

在一个地图上有NN个地窖(N \le 20)(N≤20)，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入输出格式

输入格式：

有若干行。

第1行只有一个数字，表示地窖的个数N。

第2行有N个数，分别表示每个地窖中的地雷个数。

第3行至第N+1行表示地窖之间的连接情况：

第3行有n-1个数（0或1），表示第一个地窖至第2个、第3个、…、第n个地窖有否路径连接。如第3行为011000…0，则表示第1个地窖至第2个地窖有路径，至第3个地窖有路径，至第4个地窖、第5个、…、第n个地窖没有路径。

第4行有n?2个数，表示第二个地窖至第3个、第4个、…、第n个地窖有否路径连接。

… …

第n+1行有1个数，表示第n?1个地窖至第n个地窖有否路径连接。（为0表示没有路径，为1表示有路径）。

输出格式：

有两行

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

输入输出样例:

输入样例#1：

5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

输出样例#1：

1 3 4 5
27

开始犯傻：

说实在的，考前，刚好打了一半这道题的dfs，但是考试之后打怎么也不对，于是打了个一本通的dp，我好LJ。

（1）dfs的心里路程就是定义一个bool型函数判断它还能不能挖，dfs函数部分判断如果不能继续挖下去，并且挖到的地雷数比之前的还多，就用opt记录路径pre，如果还能挖下去，就for循环找下一个能挖的地方，然后b改变标记，继续dfs，注意回溯b的标记。(码风可能有些奇怪

#include"bits/stdc++.h"
using namespace std;

inline int read() {
    int num=0,f=1;
    char c=getchar();
    for(; !isdigit(c); c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c); c=getchar()) num=num*10+c-'0';
    return num*f;
}

int n;
int ans=0;
#define N 22
int a[N];
int mp[N][N];
#define INF 0x3f3f3f3f
int pre[N];
bool b[N];
int cnt;
int opt[N];

int print(int x) {
    if(!pre[x]) cout<<pre[x]<<' ';
    else print(pre[x]);
}

bool check(int x) {
    for(int i=1; i<=n; i++)
        if(mp[x][i] && !b[i]) return false;
    return true;
}

void dfs(int x,int step,int sum) {
    if(check(x)) {
        if(sum>ans) {
            ans=sum;
            cnt=step;
            for(int i=1; i<=step; i++)
                opt[i]=pre[i];
        }
        return ;
    }
    for(int i=1; i<=n; i++) {
        if(!b[i] && mp[x][i]) {
            b[i]=1;
            pre[step+1]=i;
            dfs(i,step+1,sum+a[i]);
            b[i]=0;
        }
    }
}

void init() {
    for(int i=1; i<=n; i++) pre[i]=0;
    for(int i=1; i<=n; i++) b[i]=false;
}

int main() {
    n=read();
    init();
    for(int i=1; i<=n; i++) a[i]=read();
    for(int i=1; i<=n-1; i++) {
        for(int j=i+1; j<=n; j++) {
            cin>>mp[i][j];
        }
    }
    for(int i=1; i<=n; i++) {
        b[i]=1;
        pre[1]=i;
        dfs(i,1,a[i]);
        b[i]=0;
    }
    for(int i=1; i<=cnt; i++)
        cout<<opt[i]<<' ';
    cout<<endl<<ans;
    return 0;
}

（2）dp的心里路程是逆推，状态转移方程是f[i]=max{f[j]+h[i]}(mp[i][j]=1,i<j<=n)。

#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<cctype>
#include<list>
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 222
using namespace std;
int n;
int mp[N][N];
int h[N];
int f[N];
int ans=0;
int k=0;
int a[N];

inline int read() {
    int num=0,f=1;
    char c=getchar();
    for(; !isdigit(c); c=getchar()) if(c=='-') f=-1;
    for(; isdigit(c); c=getchar()) num=num*10+c-'0';
    return num*f;
}

int main() {
    /*  freopen("lei.in","r",stdin);
        freopen("lei.out","w",stdout);*/
    n=read();
    for(int i=1; i<=n; i++) cin>>h[i],f[i]=h[i];
    int x,y;
    /*  while(scanf("%d",&x)!=0&&scanf("%d",&y)!=0) {
            mp[x][y]=1;
        }*/
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++) {
            int ww;
            cin>>ww;
            if(ww==1)
                mp[i][j]=1;
        }
    a[n]=0;
    for(int i=n-1; i>0; i--)
        for(int j=i+1; j<=n; j++)
            if(mp[i][j]&&f[j]+h[i]>f[i]) {
                f[i]=f[j]+h[i];
                a[i]=j;
            }
    for(int i=1; i<=n; i++)
        if(ans<f[i]) {
            ans=f[i];
            k=i;
        }
    cout<<k;
    k=a[k];
    while(k) {
        cout<<" "<<k;
        k=a[k];
    }
    cout<<"\n"<<ans<<'\n';
    return 0;
}

（有木有感觉我的代码很眼熟，是的，它就是一本通的嘿嘿Q

考试总结

原文：https://www.cnblogs.com/morbidity/p/10790388.html