Bridging signals 如果f（i）只和i-1有关系 可以使用两个一维数组 交替循环

#include<stdio.h> #include<string.h> int a[2][40002]; int n; int b[40002]; int DP() { int x=1; int i; for(i=0;i<=n;i++) a[0][i]=0; while(x<=n){ int k,kk; k=x%2;kk=(x+1)%2; for(i=1;i<b[x];i++) a[k][i]=a[kk][i]; for(i=b[x];i<=n;i++) { int temp; temp=a[kk][b[x]-1]+1; if(temp>a[kk][i])a[k][i]=temp; else a[k][i]=a[kk][i]; } x++; } return 0; } int main( ) { int test; scanf("%d",&test); while(test--) { scanf("%d",&n); int i; for(i=1;i<=n;i++) scanf("%d",&b[i]); DP(); printf("%d/n",a[n%2][n]); } return 0; }