NOIP1996 第三题

<问题分析>

每个状态表示到达这个状态所挖地雷的最大数，状态转移方程 s[i]=max{s[j]}+w[i] if(v[i][j]=1)

 1 #include <stdio.h>
 2 
 3 int main()
 4 {
 5     int i,j,k,n,w[21],s[21],y[21];
 6     bool v[21][21];
 7     scanf("%d",&n);
 8     for(i=1;i<=n;i++)
 9     {
10        s[i]=0;
11        scanf("%d",&w[i]);
12     }
13     for(i=1;i<=n-1;i++)
14     {
15        for(j=i+1;j<=n;j++)
16        {
17           scanf("%d",&k);
18           if(k==1)
19             v[i][j]=true;
20           else
21             v[i][j]=false;
22        }
23     }
24     for(i=2;i<=n;i++)
25     {
26        for(j=1;j<i;j++)
27          if(v[j][i]&&s[j]+w[j]>s[i])
28          {
29             s[i]=s[j]+w[j];y[i]=j;
30          }
31     }
32     y[1]=0;
33     s[n]+=w[n];
34     i=n;j=0;
35     while(i>0)
36     {
37        w[j++]=i;
38        i=y[i];
39     }
40     for(i=j-1;i>0;i--)
41     {
42        printf("%d->",w[i]);
43     }
44     printf("%d
max=%d
",w[0],s[n]);
45     while(true);
46     return 0;
47 }