锐客网

  1. 首页 > 睿知 > it技术 > >

hdu 6049 - Sdjpx Is Happy

IT知识happy

亦余心之所善兮，虽九死其犹未悔。这篇文章主要讲述hdu 6049 - Sdjpx Is Happy相关的知识，希望能为你提供帮助。
题：
OwO http://acm.hdu.edu.cn/showproblem.php?pid=6049
(2017 Multi-University Training Contest - Team 2  - 1005)
 
解：
先预处理
mn[i][j]记录区间最小值，mx[i][j]记录区间最大值，则如果mn-mx+1和区间数字数量相同则该区间可以被归到一个小段
f[i][j]记录(i,j)段最多可以被分成几个小段，sav[i]记录从i开始的上次的可行区间的右端点
然后就可以进行求解了
设要交换的区间为seg_a,seg_b。
一开始先求seg_a的左右端点即i和j，则seg_a必须满足可行，即f[i][j]!=0，同时必须满足，seg_a为最左边的段或者seg_a左边的段包括了(1,i-1)的数字
对于每个可行的seg_a，设k为seg_a中的最大值，则
1.如果k==n的话，那么seg_b是最右边的段
2.否则seg_b右边的段为seg(k+1,n),且必须包括(k+1,n)中的所有数
然后枚举seg_b的左端点t使seg_b合法，又必须满足mn[t][k]==i，才能保证seg_a和seg_b交换后整个数列从1~n递增
（思路来自解读标程）
【hdu 6049 - Sdjpx Is Happy】（貌似是有更优解的）

hdu 6049 - Sdjpx Is Happy

文章图片
hdu 6049 - Sdjpx Is Happy

文章图片
1 #include < iostream> 2 #include < cstring> 3 #include < cstdio> 4 #include < algorithm> 5 #include < cmath> 6 7 using namespace std; 8 9 const int M=3044; 10 11 int n; 12 int s[M]; 13 int f[M][M],mn[M][M],mx[M][M]; 14 int sav[M],ans; 15 16 void init() 17 { 18memset(f,0,sizeof(f)); 19int i,j,k; 20for(i=1; i< =n; i++) 21{ 22sav[i]=i; 23f[i][i]=1; 24mn[i][i]=mx[i][i]=s[i]; 25} 26for(i=1; i< =n; i++) 27for(j=i+1; j< =n; j++) 28{ 29mx[i][j]=max(mx[i][j-1],s[j]); 30mn[i][j]=min(mn[i][j-1],s[j]); 31} 32for(i=2; i< =n; i++) 33for(j=1; j+i-1< =n; j++) 34{ 35k=j+i-1; 36if(mx[j][k]-mn[j][k]+1!=k-j+1) 37f[j][k]=0; 38else 39{ 40if(mn[j][k]< mn[j][sav[j]]) 41f[j][k]=1; 42else 43f[j][k]=f[j][sav[j]]+f[sav[j]+1][k]; 44sav[j]=k; 45} 46} 47 } 48 49 void solve() 50 { 51ans=max(1,f[1][n]); 52int i,j,k,t,tmp; 53//swap (i,j) , (t,k) 54for(i=1; i< =n; i++) 55for(j=i; j< =n; j++) 56if(f[i][j] & & (i==1 || (f[1][i-1] & & mn[1][j-1]==1)))//be sure the first seg is start from 1 or the seg(i,j) 57{ 58k=mx[i][j]; 59if(k==n || (f[k+1][n] & & mx[k+1][n]==n)) 60for(t=j+1; t< =k; t++) 61if(mn[t][k]==i & & f[t][k]) 62ans=max(ans,f[1][i-1]+1/*seg[i][j]]*/+f[j+1][t-1]+1/*seg[t][k]*/+f[k+1][n]); 63} 64 } 65 66 int main() 67 { 68int T,i,j; 69cin> > T; 70while(T--) 71{ 72scanf("%d",& n); 73for(i=1; i< =n; i++) 74scanf("%d",& s[i]); 75init(); 76solve(); 77cout< < ans< < endl; 78} 79return 0; 80 }

donnot click me 

    推荐阅读


    上一篇：在Android模拟器里安装apk

    下一篇：android中Invalidate和postInvalidate的差别