控制面板

1、ZJOI2012 灾难

TAG：拓扑排序+倍增LCA

状态：100%

 

2、巡防

TAG：树上最远点对DP做法

状态：90%

 

3、完美代价

TAG：贪心

状态：100%

 

4、cards

TAG：未知

状态：100%

 

5、set

TAG：动态规划

状态：100%

 

6、chessboard

TAG：贪心

状态：75%

 

7、HCN

TAG：搜索

状态：20%

 

8、seq

TAG：动态规划

状态：100%

 

1、ZJOI2012 灾难

　　主体思路：求出拓扑序，对于每个节点根据联通关系重新构建一棵树，直接用dep数组体现。根据这棵树直接求出以每个节点为根节点的子树大小，即答案。中间用到倍增LCA来求得这棵树。

　　首先我们自己新建一个超级生产者0号节点，所有生产者都以这个超级生产者为食物。 考虑在所有生物中建立这样一个结构： 这个结构是一颗树，一个节点代表一种生物，树上一个节点满足这个灭绝会且仅会导致以它 为根的子树灭绝。 如果我们能够建立这样一个结构，那么每个生物对应的答案可以一边 dfs 统计子树大小就得出。 

　　下面就介绍如何建立这样的结构： 首先，把所有的点按照从猎物到捕食者的顺序拓扑排序。然后依次考虑每一个生物 p，假设 在这之前已经建好了拓扑排序顺序在 p 之前的所有生物组成的上面描述的树结构。假设 p 的事物有 k 种，分别是 food[1]…food[k]（由于拓扑排序，这些点都已经在树结构中）。那么 只有 food[1]…food[k]这 k 个点的 lca 到根的路径上的点会导致 p 灭绝。于是，就可以把 p 作 为 food[1]…food[k]这 k 个点的 lca 的儿子。 具体实现上，lca 用倍增维护即可，每次新加一个点，都可以一遍倍增把新加的点的倍增数 组得到。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 #define MAXN 70005 7 #define pb push_back 8  9 int n, x, list[MAXN], f[MAXN][16], dep[MAXN], ans[MAXN], cnt[MAXN], tot; 10 11 vector 
        
          edge[MAXN], edge2[MAXN];12 13 int LCA(int x, int y)14 {15     int o;16     if (dep[x] < dep[y]) swap(x, y);17     for (o = 0; (1 << o) <= dep[x]; o++); o--;18     for (int i = o; i >= 0; i--)19         if (dep[x] - (1 << i) >= dep[y]) x = f[x][i];20     if (x == y) return x;21     for (int i = o; i >= 0; i--)22         if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];23     return f[x][0];24 }25 26 int main()27 {28     freopen("catas.in", "r", stdin);29     freopen("catas.out", "w", stdout);30     scanf("%d", &n);31     for (int i = 1; i <= n; i++)32     {33         int lf = 1;34         scanf("%d", &x);35         while (x) edge[i].pb(x), edge2[x].pb(i), scanf("%d", &x), lf = 0;36         if (lf) edge[i].pb(0), edge2[0].pb(i);37     }38     for (int i = 1; i <= n; i++) cnt[i] = edge[i].size();39     for (int i = 0; i <= n; i++)40     {41         int o = list[i];42         for (int x = 0; x < edge2[o].size(); x++)43         {44             int v = edge2[o][x];45             if (!--cnt[v]) list[++tot] = v;46         }47     }48     for (int i = 1; i <= n; i++)49     {50         int o = list[i], lca = -1;51         for (int x = 0; x < edge[o].size(); x++)52         {53             int v = edge[o][x];54             lca = lca == -1 ? v : LCA(lca, v);55         }56         dep[o] = dep[lca] + 1, f[o][0] = lca;57         for (int j = 1; j <= 15; j++) f[o][j] = f[f[o][j - 1]][j - 1];58     }59     for (int i = 0; i <= n; i++) ans[i] = 1;60     for (int i = n; i >= 0; i--) ans[f[list[i]][0]] += ans[list[i]];61     for (int i = 1; i <= n; i++) printf("%d\n", ans[i] - 1);62     return 0;63 }
        
       
      
     

 

 

 

 

2、巡防

　　首先看如果要求从某村庄出发访问所有的村庄最后还要回来 那答案显然是所有边权之 和乘以 2（每条边都是一去一回） 现在不要求回来的话就是省掉了从某个点回到起点的这么条路径，显然这个路径越长越 靠谱，所以从某点出发的答案就是边权和乘 2 减去这个点到它最远点的距离。 然后就是树上的最远点对。这就化归到了一个经典模型上。 

1 #include 
     
       2 #include 
      
        3 #define MAXN 100005 4  5 int max(int a, int b) { return a > b ? a : b; } 6  7 struct Edge { int v, next, w; } edge[MAXN << 1]; 8  9 int now, h[MAXN], n, u, v, w, dis[MAXN], vis[MAXN], maxw, maxp, f[MAXN], ans, sum, get[MAXN];10 11 void addEdge(int u, int v, int w) { now++, edge[now] = (Edge) {v, h[u], w}, h[u] = now; }12 13 void DFS(int o, int w)14 {15     if (w > maxw) maxw = w, maxp = o;16     for (int x = h[o]; x; x = edge[x].next)17     {18         int v = edge[x].v;19         if (!vis[v]) vis[v] = 1, get[v] = 1, DFS(v, w + edge[x].w), vis[v] = 0;20     }21 }22 23 void DFS2(int o, int w)24 {25     dis[o] = max(dis[o], w);26     if (w > maxw) maxw = w, maxp = o;27     for (int x = h[o]; x; x = edge[x].next)28     {29         int v = edge[x].v;30         if (!vis[v]) vis[v] = 1, DFS2(v, w + edge[x].w), vis[v] = 0;31     }32 }33 34 int main()35 {36     freopen("path.in", "r", stdin);37     freopen("path.out", "w", stdout);38     scanf("%d", &n);39     for (int i = 1; i <= n - 1; i++) 40         scanf("%d %d %d", &u, &v, &w), addEdge(u, v, w), addEdge(v, u, w), sum += w << 1;41     for (int i = 1; i <= n; i++) scanf("%d", &f[i]);42     for (int i = 1; i <= n; i++) if (f[i]) { get[i] = 1, DFS(i, 0); break; }43     for (int i = 1; i <= n; i++) if (!get[i]) printf("-1"), exit(0);44     DFS2(maxp, 0), DFS2(maxp, 0);45     for (int i = 1; i <= n; i++) ans = (dis[i] > ans && f[i]) ? dis[i] : ans;46     printf("%d", sum - ans);47     return 0;48 }
      
     

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define MAXN 200005 5 using namespace std; 6 int n; 7 int totaledge,point[MAXN],v[MAXN],w[MAXN],next[MAXN]; 8 int f[MAXN][2]; 9 int g[MAXN][2];10 int ans[MAXN];11 void addedge(int x,int y,int z){12     totaledge++;13     v[totaledge] = y;14     w[totaledge] = z;15     next[totaledge] = point[x];16     point[x] = totaledge;17 }18 void dfs1(int fa, int x){19     int i,j;20     for (i=point[x];i;i=next[i]){21         if (v[i] == fa) continue;22         dfs1(x, v[i]);23         j = f[v[i]][0] + w[i];24         if (j>f[x][0]){25             f[x][1] = f[x][0];26             g[x][1] = g[x][1];27             f[x][0] = j;28             g[x][0] = v[i];29         }30         else if (j>f[x][1]){31             f[x][1] = j;32             g[x][1] = v[i];33         }34     }35 }36 void dfs2(int fa, int x,int y){37     int i,j;38     ans[x] = max(f[x][0],y);39     for (i=point[x];i;i=next[i]){40         if (v[i] == fa) continue;41         if (g[x][0]!=v[i]) dfs2(x, v[i],max(y,f[x][0])+w[i]);42             else dfs2(x, v[i],max(y,f[x][1])+w[i]);43     }44 }45 int d[MAXN];46 char str[20];47 int main(){48     int i,x,y,z, t, ri;49 //    for (ri = 0; ri < 30; ri++){50 //        sprintf(str, "%d.in", ri);51        freopen("path.in", "r", stdin);52 //        sprintf(str, "%d.out", ri);53        freopen("path.out", "w", stdout);54         scanf("%d",&n);55         memset(point,0,sizeof(point));56         totaledge = t = 0;57         for (i=2;i<=n;i++){58             scanf("%d%d%d",&x,&y, &z);59             addedge(x,y,z);60             addedge(y,x,z);61             t += z + z;62         }63         z = 0;64         for (i = 1; i <= n; i++){65             scanf("%d", &d[i]);66             z += d[i];67         }68         if (z == 0){69             printf("-1\n");70             return 0;71         }72         dfs1(0, 1);73         dfs2(0, 1, 0);74         z = 0;75         for (i=1;i<=n;i++){76             if (d[i]) z = max(z, ans[i]);77         }78         printf("%d\n", t - z);79 //    }80     return 0;81 }
       
      
     

 

3、完美代价

注意到这个问题可以这样考虑： 假设相同字符之间也是有区别的。那么字符串可以看做一个排列。如果答案是已知的一 个排列 P，则任务就是求从 (1,2,...,n) 变换到排列 P 需要多少次操作。

很明显，最优的方案要求每次使逆序对个数 +1 。很明显，一种最优的方法就是一开始就 将排列的第一个位置和最后一个位置放好，之后再对剩下的部分做变换。那么相对应的，也 有一种方法是最后才将排列的第一个位置和最后一个位置弄好。考虑使用这种方法。 假设现在要处理字符串的第一个字符和最后一个字符，他们分别为 A 和 B，并且我们用 C 来替代。由于 C 一定要移动到和 A, B 相邻的位置，所以如下图：

+-------+

|           |

|           |

AC ... CB

明显，如果 C ≠ A,B ，则交换 AC 和 CB 后方案是不合法的，因此 C 一定是 A,B 中的 一个。

那么再回到一开始的先处理头尾的情况。容易知道 C 要和 A, B 相等，因此我们只需要 找到离 A 最近的 B 以及离 B 最近的 A，判断哪个更近即可。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 char s[10010]; 8 int n, cnt; 9 10 int main()  {11     freopen("reference.in","r",stdin);  freopen("reference.out","w",stdout); 12   scanf("%d", &n);13   scanf("%s", s + 1);14   15   int x = 0, y = n + 1;16   while (++x < --y)  {17     if (s[x] == s[y])18       continue;19     int nx = x + 1, ny = y - 1;20     while (s[nx] != s[y])21       ++nx;22     while (s[ny] != s[x])23       --ny;24     if (nx == y  &&  ny == x)  {25       printf("Impossible");26       return 0;27     }28     if (nx - x <= y - ny  &&  nx != y)29       for (int i = nx; i > x; --i)30     swap(s[i], s[i - 1]), ++cnt;31     else32       for (int i = ny; i < y; ++i)33     swap(s[i], s[i + 1]), ++cnt;34   }35   printf("%d\n", cnt);36 }
        
       
      
     

 

1 #include 
     
       2 #define MAXN 8005 3  4 int n, tot[30], totx, x; 5 char ch[MAXN]; 6  7 int work() 8 { 9     int res = 0;10     for (int i = 0; i <= (n >> 1); i++)11         if (ch[i] == x)12            { 13             for (int j = i; j < n - i - 1; j++) 14                 if (ch[n - i - 1] == ch[j]) 15                 {16                     res += j - i; 17                     for (int k = j; k > i; k--) ch[k] = ch[k - 1];18                     ch[i] = ch[n - i - 1]; 19                     break; 20                 }21            }22            else 23            { 24                for (int j = n - i - 1; j >= i; j--) 25                    if (ch[i] == ch[j]) 26                 { 27                     res += n - i - 1 - j; 28                        for (int k = j; k < n - i - 1; k++) ch[k] = ch[k + 1]; 29                        ch[n - i - 1] = ch[i]; 30                        break; 31                 }32            }33     return res;34 }35 36 int main()37 {38     freopen("reference.in", "r", stdin);39     freopen("reference.out", "w", stdout);40     scanf("%d %s", &n, ch);41     for (int i = 0; i <= n - 1; i++) tot[ch[i] - 'a']++;42     for (int i = 0; i <= 25; i++) if (tot[i] % 2) totx++, x = i + 'a';43     if (totx >= 2) printf("Impossible"); else printf("%d", work());44     return 0;45 }
     

 

4、cards

假设最后 xxxxxx..xxxxxx 被分成了 y 块 那么要在其中找 y-1 个位置插入 o 然后我们发现这 y-1 个位置会决定减去的分数 而在 y-1 个位置怎么放 o 会决定加上的分数 这两者是独立的

考虑怎么找这 y-1 个位置 显然是越平均越好 比如说将 4 分成两份 1+3*3>2*2+2*2

在 y-1 个位置怎么放呢 显然是 y-2 个位置中放一个 o 剩下一个位置放剩余的 o 和放 x 的原理是一样的

然后需要注意下 y=1 的情况

枚举 y 即可

 

1 #include 
     
       2 #define INF 1ll << 60 3  4 typedef long long ll; 5  6 ll a, b, ans = -INF, x; 7  8 ll get(ll o) 9 {    10     ll s = b / (o + 1), v = b % (o + 1);11     ll f1 = v * (s + 1) * (s + 1) + (o + 1 - v) * s * s, f2 = o ? (a - o + 1) * (a - o + 1) + o - 1 : (a - o) * (a - o) + o;12     return f2 - f1;13 }14 15 int main()16 {17     freopen("cards.in", "r", stdin);18     freopen("cards.out", "w", stdout);19     scanf("%d %d", &a, &b);20     for (ll i = 0; i <= a; i++) 21     {22         ll o = get(i);23         if (o > ans) ans = o, x = i;24     }25     printf("%I64d\n", ans);26     ll s = b / (x + 1), v = b % (x + 1);27     if (!x)28     {29         for (ll i = 1; i <= b; i++) printf("x");30         for (ll i = 1; i <= a; i++) printf("o");31     }32     else33     {34         for (ll i = 1; i <= v; i++)35         {36             for (ll j = 1; j <= s + 1; j++) printf("x");37             printf("o");38         }39         for (ll i = 1; i <= x - v; i++)40         {41             for (ll j = 1; j <= s; j++) printf("x");42             printf("o");43         }44         for (ll i = 1; i <= a - x; i++) printf("o");45         for (ll i = 1; i <= s; i++) printf("x");46     }47     return 0;48 }
     

 

 

 

 

5、set

注意到我们计数的状态有对成型，即：一个A胜利的局面恰好唯一对应一个B胜利的局面（双射为交换双方状态）。

那么，我们只需要考虑AB平局的状态，用总状态数减去平局状态并除以2就能得到A胜利的状态数。

由于异或有自反性，所以AB平局的局面两者得到的权值的异或值为0.

以f[i][j]表示第i个数，现在两者得到的权值的异或值为j的方案数：

f[i][j] = f[i - 1][j] + f[i - 1][j ^ a[i]] + f[i - 1][j ^ a[i]]

则答案为1 / 2 * (3的n次方 - f[n][0])。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 #define ll long long 6 #define FOR( A, B, C ) for ( int A = B, _end_ = C; A <= _end_; A++ ) 7  8 int f[ 4096 ][ 4096 ], n, a[ 4096 ], P = 1998585857; 9 10 int fpm( int F, int FF, int P ) {11     int ans = 1;12     for ( ; FF; FF >>= 1, F = (ll)F * F % P )13         if ( FF & 1 ) ans = (ll)ans * F % P;14     return ans;15 }16 17 int main() {18     freopen( "set&set.in", "r", stdin );19     freopen( "set&set.out", "w", stdout );20     21     scanf( "%d", &n );22     FOR ( i, 1, n ) { scanf( "%d", &a[ i ] ); }23     24     f[ 0 ][ 0 ] = 1;25     FOR ( i, 1, n ) {26         FOR ( j, 0, 4095 ) {27             f[ i ][ j ] = ( f[ i - 1 ][ j ] + ( (ll)f[ i - 1 ][ j ^ a[ i ] ] << 1 ) ) % P;28         }29     }30     31     int ans = ( (ll)fpm( 3, n, P ) - f[ n ][ 0 ] + P ) % P; ans = (ll)ans * fpm( 2, P - 2, P ) % P;32     33     printf( "%d\n", ans );34 }
      
     

 

6、chessboard

其实这个问题可以用贪心能解决，以横轴为例，假设扫描到了i，将左端点<=i的区间都加入一个集合，然后在已经加入的区间集合中选取一个右端点最小的区间来作为i的匹配区间即可。用堆优化或者set。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 #define MAXN 100005 7  8 int n, a[MAXN], b[MAXN], c[MAXN], d[MAXN], ansx[MAXN], ansy[MAXN], h[MAXN], next[MAXN], md; 9 10 struct cmp11 {12     bool operator () (int x, int y)13     {14         return md ? (d[x] < d[y] || (d[x] == d[y] && x < y)) : (c[x] < c[y] || (c[x] == c[y] && x < y));15     }16 };17 18 set 
        
          st;19 20 bool work1()21 {22     int get = 0; md = 0;23     st.clear(), memset(h, 0, sizeof(h));24     for (int i = 1; i <= n; i++) 25         next[i] = h[a[i]], h[a[i]] = i;26     for (int i = 1; i <= n; i++)27     {28         for (int x = h[i]; x; x = next[x]) st.insert(x);29         while (!st.empty())30         {31             int o = *st.begin(); st.erase(o);32             if (c[o] < i) continue;33             ansx[o] = i, get = 1;34             break;35         }36         if (!get) return 0;37     }38     return 1;39 }40 41 bool work2()42 {43     int get = 0; md = 1;44     st.clear(), memset(h, 0, sizeof(h));45     for (int i = 1; i <= n; i++) 46         next[i] = h[b[i]], h[b[i]] = i;47     for (int i = 1; i <= n; i++)48     {49         for (int x = h[i]; x; x = next[x]) st.insert(x);50         while (!st.empty())51         {52             int o = *st.begin(); st.erase(o);53             if (d[o] < i) continue;54             ansy[o] = i, get = 1;55             break;56         }57         if (!get) return 0;58     }59     return 1;60 }61 62 int main()63 {64     freopen("chessboard.in", "r", stdin);65     freopen("chessboard.out", "w", stdout);66     scanf("%d", &n);67     for (int i = 1; i <= n; i++) 68         scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);69     if (work1() && work2()) 70         for (int i = 1; i <= n; i++) printf("%d %d\n", ansx[i], ansy[i]); 71     else printf("%d", -1);72     return 0;73 }
        
       
      
     

 

7、HCN

大搜索题。首先，对于一个数a，由唯一分解定律一定可以分为a = p1 ^ c1 * p2 ^ c2 * ...* pn ^ cn，且其因子个数为。第一步，对于一组给定的c，显然我们应该把较大的ci分给较小的质数，这样可以得到更小的a。从而应该把c由大到小分配给前n个质数。

只是这样写就能解决n <= 10 ^ 18的部分了。接下来的部分就要写高精度了。

为了降低计算量，我们考虑加入最优化剪枝：

1、当c1确定时，我们在考虑当前第i个素数的指数时，存在一个上界c1 / ki，其中ki表示最大的满足2 ^ ki <= pri[i]的数，当ci比其更大时，不如ci -= 1，c1 += ki。

2、同样地方法，我们也能得到它的一个上界(c1 - 2 * ki - 1) / (1 + ki)，表示ci比其更小时，不如c1 -= ki，ci += 1

3、以上两个剪枝的关键都在于没有办法给2进行剪枝，所以我们可以考虑如何限制住c1.我们可以考虑用满足来进行对一个素数的剪枝。令ti表示最大的满足pri[i]^ti <= pri[n + 1]的数，当ci > 2 * ti时，不如把ci -= ti，c[n + 1] += 1。

呕。

 

1 #include 
     
        2 #include 
      
         3   4 #define MAX 30  5 #define MAXX 205  6 #define LEN 100000000  7   8 typedef long long ll;  9  10 int max1(int a, int b) { return a > b ? a : b; } 11  12 int min1(int a, int b) { return a < b ? a : b; } 13  14 ll max; 15  16 int pri[MAXX], ptop, top, s[MAXX], dig = LEN, q[MAXX], k[MAXX]; 17  18 struct ubInt 19 { 20     ll num[MAX + 1]; 21     int fir; 22      23     void init(int x) { num[fir = MAX] = x; } 24      25     void clear() { for (int i = fir; i <= MAX; i++) num[i] = 0;    fir = MAX; } 26      27     void exceed()  28     { 29         int i = MAX, j = 0; 30         for (; i >= fir || j; i--)  31         { 32             num[i] += j, j = 0; 33             if (num[i] >= dig) j = num[i] / dig, num[i] %= dig; 34         } 35         fir = i + 1; 36     } 37      38     void operator *= (const int x)  39     { 40         for (int i = fir; i <= MAX; i++) num[i] *= x; 41         exceed(); 42     } 43      44     void operator = (const ubInt &x)  45     { 46         clear(); 47         for (int i = x.fir; i <= MAX; i++) num[i] = x.num[i]; 48         fir = x.fir; 49     } 50      51     void read()  52     { 53         char ch[MAXX]; int l; 54         scanf("%s", ch), l = strlen(ch); 55         int j = 1; fir = MAX; 56         for (int i = l - 1; i >= 0; i--) 57         { 58             num[fir] += (ch[i] - '0') * j, j *= 10; 59             if (j == dig) j = 1, fir--; 60         } 61         if (j == 1) fir++; 62     } 63      64     void print()  65     { 66         printf("%I64d", num[fir]); 67         for (int i = fir + 1; i <= MAX; i++) printf("%08I64d", num[i]); 68         printf("\n"); 69     } 70 }; 71  72 ubInt ans, n, now[MAXX + 10]; 73  74 int operator < (const ubInt &a, const ubInt &b) 75 { 76     if (a.fir != b.fir) return a.fir > b.fir; 77     for (int i = a.fir; i <= MAX; i++) 78         if (a.num[i] != b.num[i]) return a.num[i] < b.num[i]; 79     return 0; 80 } 81  82 void init() { 83 #define MMM 300 84     int t[MMM + 10]; 85     max = 1, ans.init(1); 86     for (int i = 1; i <= MAX; i++) now[i].fir = MAX; 87     now[1].num[MAX] = 1; 88     for (int i = 2; i <= MMM; i++) t[i] = 0; 89     for (int i = 2; i <= MMM; i++) 90         if (!t[i])  91         { 92             pri[++ptop] = i; 93             for (int j = 2; j * pri[ptop] <= MMM; j++) t[j * pri[ptop]] = 1; 94         } 95     ubInt e; e.fir = 0, e.clear(), e.init(1); 96     for (int i = 1; i <= ptop; i++) 97     { 98         e *= pri[i]; 99         if (n < e) { top = i - 1; break; }100     }101     for (int i = 1; i <= top; i++)102     {103         int tmp = 1;104         for (int j = 0; j <= 100; j++)105         {106             if (tmp > pri[top]) { s[i] = j - 1; break; }107             tmp *= pri[i];108         }109     }110     for (int i = 1; i <= top; i++)111     {112         int tmp = 1;113         for (int j = 0; j <= 100; j++)114         {115             if (tmp > pri[i]) { k[i] = j - 1; break; }116             tmp <<= 1;117         }118     }119 }120 121 void brute(int v, ll get, int r3) 122 {123     if (n < now[v]) return;124     else if (get > max  ||  (get == max  &&  now[v] < ans)) max = get, ans = now[v];125     if (v > top) return;126     int l = 1, r1 = 1 << 30, r2;127     if (v != 1) l = (q[1] - (k[v] << 1) - 1) / (1 + k[v]) + 1, r1 = q[1] / k[v];128     r2 = s[v] << 1 | 1;129     now[v + 1] = now[v];130     for (int i = 1; i <= max1(l, 1) - 1; i++) now[v + 1] *= pri[v];131     for (int i = max1(l, 1); i <= min1(min1(r1, r2), r3); i++)132         now[v + 1] *= pri[v], q[v] = i, brute(v + 1, get * (i + 1), i);133 }134 135 int main() 136 {137     freopen("HCN.in", "r", stdin);138     freopen("HCN.out", "w", stdout);139     n.read(), init(), brute(1, 1, 100), ans.print();140     return 0;141 }
      
     

 

 

 

 

8、seq

考虑已经有了一个子序列 我现在要在后面加入一个数 a[i] 如果能加说明不存在二元组（s，t）满足 a[s]<a[t]<a[i] 二元组有很多我们需要关心的其实只是最小的 a[t]

那么加进去一个数字以后最小的 a[t]可能发生改变 那么如何判断加进去的 a[i]能否成为最小的 a[t]呢 只需要知道没加进 a[i]时的子序列的最小值

那么 dp 的思路就建立了

令 f[i][j][l]表示考虑了前 i 个数 子序列中最小值为 j 子序列中最小的 a[t]为 l

 

1 #include 
     
       2 #define MAXN 205 3 #define MOD 1000000007 4  5 int n, a[MAXN], f[MAXN][MAXN][MAXN], ans; 6  7 void upd(int &a, int b) { (a += b) %= MOD; } 8  9 int main()10 {11     freopen("seq.in", "r", stdin);12     freopen("seq.out", "w", stdout);13     scanf("%d", &n);14     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);15     f[0][n + 1][n + 1] = 1;16     for (int i = 0; i < n; i++)17         for (int j = 1; j <= n + 1; j++)18               for (int l = 1; l <= n + 1; l++)19                 if (f[i][j][l])20                 {21                       upd(f[i + 1][j][l], f[i][j][l]);22                       if (a[i + 1] > l) continue;23                       if (a[i + 1] > j) upd(f[i + 1][j][a[i + 1]], f[i][j][l]);24                       if (a[i + 1] < j) upd(f[i + 1][a[i + 1]][l], f[i][j][l]);25                 }26     for (int j = 1; j <= n; j++)27         for(int l = 1; l <= n + 1; l++) upd(ans, f[n][j][l]);28     printf("%d", ans);29     return 0;30 }