贪心,这里提一下dilworth定理很厉害()
@:因为要消除多算的一次,由dilworth定理将题目从最少不降序列划分转为最长下降子序列,若a.w>b.w则在二分计算时会多算一次,因为实际上两者l是相等的(注意这里下降定义为l,w同时小于),所以通过将小者放在前面,来出去多算的一次。
#include#include using namespace std;int a,b,len,k[5000];struct node{ int l,w;}m[5000];bool cmp(node a,node b){ if(a.l==b.l) return a.w >1; if(k[t]==key) return t; else if(k[t] m[i].w) k[++len]=m[i].w; else k[t]=m[i].w; } return len+1;}int main(){ scanf("%d",&a); for(int i=0;i