锐客网

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

hdu6049---Sdjpx Is Happy(区间DP+枚举)

IT知识区间DP区间

白日放歌须纵酒，青春作伴好还乡。这篇文章主要讲述hdu6049---Sdjpx Is Happy(区间DP+枚举)相关的知识，希望能为你提供帮助。
【hdu6049---Sdjpx Is Happy(区间DP+枚举)】题目链接
 
Problem Description Sdjpx is a powful man,he controls a big country.There are n soldiers numbered 1~n(1< =n< =3000).But there is a big problem for him.He wants soldiers sorted in increasing order.He find a way to sort,but there three rules to obey.
1.He can divides soldiers into K disjoint non-empty subarrays.
2.He can sort a subarray many times untill a subarray is sorted in increasing order.
3.He can choose just two subarrays and change thier positions between themselves.
Consider A = [1 5 4 3 2] and P = 2. A possible soldiers into K = 4 disjoint subarrays is:A1 = [1],A2 = [5],A3 = [4],A4 = [3 2],After Sorting Each Subarray:A1 = [1],A2 = [5],A3 = [4],A4 = [2 3],After swapping A4 and A2:A1 = [1],A2 = [2 3],A3 = [4],A4 = [5].
But he wants to know for a fixed permutation ,what is the the maximum number of K?
Notice: every soldier has a distinct number from 1~n.There are no more than 10 cases in the input.   Input First line is the number of cases.
For every case:
Next line is n.
Next line is the number for the n soildiers.   Output the maximum number of K.
Every case a line.   Sample Input251 5 4 3 2 54 5 1 2 3  Sample Output42     题意：输入一个1~n的排列，现在要求通过以下三种动作将之变成一个单调上升的序列，三种动作如下：           1、将这个序列分成K段           2、可以将任意一个段中的数进行排序，使之变成上升的序列（可以对多个段进行操作）     3、可以对其中的两个段交换位置，只能交换一次           求最大的K值？   思路：定义f[i][j]表示 i 到 j 之间的区间能分成多少个合法的段（合法的段表示这个区间中的数排序后是一个连续的数列，f[i][j]表示段内排好序后，段与段之间也是保持连续的如段312 和 465 ，123456连续）， 通过区间DP可以求出所有 f[i][j]，还需要求出每个区间的最大值最小值 mx[][] , mn[][] , 之后枚举所有的子区间。           对于其中每一个子区间[i,j] , 如果f[i][j]> 0，那么就表示i到j排完序后是连续的，否则直接枚举计算下一个区间。当 f[i][j]> 0，k=mx[i][j] , 那么区间[i,j]应该和[t,k]区间进行交换位置，t目前还不确定，所以需要枚举t （j< t< =k）, 那么必须有： f[1][i-1] > 0& & mn[1][i-1]=1 或者i==1   ，mn[t][k]=i，f[k+1][n]> 0 & & mx[k+1][n]=n 或者 k==n ，ans=max(ans,f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n])  。

代码如下：

#include < iostream> #include < algorithm> #include < cstdio> #include < cstring> using namespace std; const int N=3e3+5; int f[N][N]; int mx[N][N],mn[N][N],R[N]; int main() { ///cout < < "Hello world!" < < endl; int T; cin> > T; while(T--) { int n; scanf("%d",& n); memset(f,0,sizeof(f)); for(int i=1; i< =n; i++) { scanf("%d",& mx[i][i]); mn[i][i]=mx[i][i]; f[i][i]=1; R[i]=i; } for(int i=1; i< =n; i++) { for(int j=i+1; j< =n; j++) { mx[i][j]=max(mx[i][j-1],mx[j][j]); mn[i][j]=min(mn[i][j-1],mn[j][j]); } } for(int i=2; i< =n; i++) { for(int j=1; j+i-1< =n; j++) { int k=j+i-1; if(mx[j][k]-mn[j][k]+1!=i) f[j][k]=0; else { if(mn[j][k]!=mn[j][R[j]]) f[j][k]=1; else f[j][k]=f[j][R[j]]+f[R[j]+1][k]; R[j]=k; } } } int ans=f[1][n]; for(int i=1; i< =n; i++) { for(int j=i; j< =n; j++) { if(!f[i][j]) continue; if(i==1 || (f[1][i-1]& & mn[1][i-1]==1)) { int k=mx[i][j]; if(k==n || (f[k+1][n]& & mx[k+1][n]==n)) { for(int t=j+1; t< =k; t++) { if(f[t][k]& & mn[t][k]==i) ans=max(ans,f[1][i-1]+1+f[j+1][t-1]+1+f[k+1][n]); } } } } } printf("%d\n",ans); } return 0; }

 
           

    推荐阅读


    上一篇：Codeforces461AAppleman and Toastman 贪心

    下一篇：[Android] SQLite数据库之增删改查基础操作