DP。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7  8 #define MAXN 105 9 int score[MAXN];10 bool map[MAXN][MAXN];11 int path[MAXN];12 int dp[MAXN];13 14 void print_path(int x) {15     if (path[x] != 0)16         print_path(path[x]);17     printf("%d->", x);18 }19 20 int main() {21     int t, n, m;22     int i, j, k, tmp;23 24 #ifndef ONLINE_JUDGE25     freopen("data.in", "r", stdin);26 #endif27 28     scanf("%d", &t);29     for (k=1; k<=t; ++k) {30         scanf("%d", &n);31         for (i=1; i<=n; ++i)32             scanf("%d", &score[i]);33         score[n+1] = 0;34         memset(map, false, sizeof(map));35         memset(dp, 0, sizeof(dp));36         memset(path, 0, sizeof(path));37         scanf("%d", &m);38         while (m--) {39             scanf("%d %d", &i, &j);40             map[i][j] = true;41         }42         for (i=1; i<=n+1; ++i) {43             int max = 0, v = 0;44             for (j=1; j
          
           = max) {46 max = dp[j];47 v = j;48 }49 }50 dp[i] = max + score[i];51 path[i] = v;52 }53 printf("CASE %d#\n", k);54 printf("points : %d\n", dp[n+1]);55 printf("circuit : ");56 print_path(path[n+1]);57 printf("1\n");58 if (k != t)59 printf("\n");60 }61 62 return 0;63 }