[luoguP1415] 拆分数列（DP）

传送门

t(i,j)表示下标从i到j的数

d[i]表示以i结尾的最小的数的下标

d[i]=max(j) (1<=j<=i && t(d[j1],j1)<t(j,i))

这样从1到n一遍DP可以求出末尾最小的数

f[i]表示以i开头的最大的数的下标

f[i]=max(j) (i<=j<=n && t(i,j)<t(j+1,d[j+1]))

边界为f[d[n]]=n

这样从d[n]1到1一遍DP可以求出开头最大的数，第二个最大的数。。。

注意前导0的情况

#include <cstdio>#include <cstring>#define N 1001int n;char s[N];int d[N], f[N];//d[i]表示以i结尾的数，满足条件的最小数 //f[i]表示以i开头的数，满足条件的最大数 //s[i][j]表示从i到j的数是多少 inline int cmp(int x1, int y1, int x2, int y2)return 0;}if(y1  x1 > y2  x2) return 1;if(y1  x1 < y2  x2) return 2;}int main()while(s[d[n]  1] == '0') d[n];for(i = d[n]; i <= n; i++) f[i] = n;for(i = d[n]  1; i >= 1; i)if(cmp(1, n, d[n], n) == 0)j = 1;while(j <= n)return 0;}

上一篇：[luoguP2331] [SCOI2005]最大子矩阵（DP）

下一篇：[luoguP2051] [AHOI2009]中国象棋（DP）