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

2018-06-17 22:08:30来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

 

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 Input
2
5
1 5 4 3 2
5
4 5 1 2 3
 
Sample Output
4
2
 
 
题意:输入一个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;
}

 

          

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P2742 [USACO5.1]圈奶牛Fencing the Cows

下一篇:C++ DWORD 转byte char 数组、指针