问题标题: 酷町堂：5583 营救家人（save）

题目描述 Description

北境统领史塔克家族的部分家人被兰尼斯特家族软禁。为了营救家人，北境之王罗柏●史塔克准备率领众多北境领主攻伐兰尼斯特家族。北境共有n个领主，每个领主都住在自己的城堡里面，每个城堡都屯有一定数量的士兵。 由于地形、经济条件等原因，只有部分城堡之间有道路连接。罗柏●史塔克想汇总领主的兵力，他可以选择从任一城堡出发,并沿着道路向后面的城堡进发(从第i号城堡只能向第i+1到第n号城堡进发)，当没有后续城堡时，完成兵力的集中。请你设计一个汇总兵力的方案，使得罗柏.史塔克能集中最多的兵力。

输入描述 Input Description

有n+1行。第1行只有一个数字，表示城堡的个数n。第2行有n个数，分别表示每个城堡中的士兵个数。第3行至第n+1行表示城堡之间的道路连接情况，0表示没有道路，1表示有道路。如第3行有n-1个数，表示第1个城堡至第2个、第3个、.第n个城堡是否有道路连接。后面以此类推。

输出描述 Output Description

有两行数据。第一行表示最优方案中访问城堡序号的排列，各序号间以一个空格分隔，没有多余的空格。第二行只有一个数，表示能集中到的最多的士兵数量。

爆0了

#include<iostream>
#include<bits/stdc++.h>
#pragma GCC optimize(3) 
using namespace std;
int n,ans,s;
int vis[25],path[25],a[25],f[25];
bool dis[25][25];
void dfs(int pos,int sum,int cnt){
    if(sum>ans){
        ans=sum;
        for(int i=1;i<=cnt;i++) path[i]=vis[i];
        s=cnt;
    }
    if(sum+f[pos]<ans) return ;
    vis[cnt]=pos;
    sum+=a[pos];
    for(int i=pos+1;i<=n;i++){
        if(dis[pos][i]){
            vis[cnt+1]=i;
            dfs(i,sum+a[i],cnt+1);
            vis[cnt+1]=0;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i>=1;i--){
        f[i]=f[i+1]+a[i];
    }
    for(int i=1;i<=n-1;i++){
        int pos=i+1;
        for(int j=1;j<=n-i;j++){
            int x;
            cin>>x;
            dis[i][pos]=dis[pos][i]=x;
            pos++;
        }
    }
    dfs(1,0,0);
    cout<<1<<" ";
    for(int i=1;i<=s;i++){
        cout<<path[i]<<" ";
    }
    cout<<endl<<ans;
    return 0;
}