https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5156

is there O(N^2) solution???

I have used at least three approach to solve this problem.first two get TLE, last one AC 50 ms(the time is surprising me,because I use O(n^3) precal +constant optimizition..

the second one I use O(n^2)precal +O(n^2*log(n)) FFT obviously it will TLE because there are 1500 test cases..

the third one I use O(n^3) dp[0][i][j][s] record to fill first i empty cells,there are j numbers which is smaller than a1 and s numbers bigger than a(i+1) and ai<a(i+1) dp[1][i][j][s] means ai>a(i+1). in order to get O(1)transfer we can recodrd sum[0][i][j][s]..

to speed up the process of O(N^3) we only need to record states that is visit by the input,so I sort the input increasing by n use scroll array. use f[2002][2002] record f[n][a1-1]=max(f[n][a1-1],n-an)

for(i=1998;i>=0;i--)
                        for(j=i;j>=0;j--)
                           f[i][j]=max(f[i][j],f[i+1][j]-1);

for each first two state (i,j) the third state that visit is only [0,min(i-j,f[i][j])], this speed up made my code 50ms..