【noip模拟题】迎接仪式（dp+特殊的技巧）-白红宇

【noip模拟题】迎接仪式（dp+特殊的技巧）

阅读量：6525 次

发布时间：2019-06-24

本文共 2309 字，大约阅读时间需要 7 分钟。

好神的一题。。。

这是一道DP题,本题的难点在于状态的确定,由于调整是任意的,很难划分状态,我们略微修改一下调整的形式:把一次’j’和’z’交换看做两次变换:’j’->’z’;’z’->’j’ (zz交换和jj交换是没有意义的,不作考虑);于是最多’j’->'z' 'z'->'j'各K次.

F[i,j,k]:=F[i-2,j-x,k-y]+1;

If A[i-1]=j then x=0 else x=1

If A[i]=z then y=0 else y=1

然后最后要看是否有那么多个j和z能够变换。

orz

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef long long ll;#define pii pair
              
               #define mkpii make_pair
               
                #define pdi pair
                
                 #define mkpdi make_pair
                 
                  #define pli pair
                  
                   #define mkpli make_pair
                   
                    #define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a
                    
                     =t1 && y>=t2) f[i][x][y]=max(f[i][x][y], f[i-2][x-t1][y-t2]+1); if(x==y) ans=max(ans, f[i][x][y]); } printf("%d\n", min(ans, min(mn1, mn2))); return 0;}

【问题描述】

LHX教主要来X市指导OI学习工作了。为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。

为了简单描述这个不和谐的队列，我们用“j”替代“教”，“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。为了让教主看得尽量舒服，你必须调整队列，使得“jz”子串尽量多。每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。而因为教主马上就来了，时间仅够最多作K次调整（当然可以调整不满K次），所以这个问题交给了你。

【输入格式】

输入文件welcome.in的第1行包含2个正整数N与K，表示了序列长度与最多交换次数。

第2行包含了一个长度为N的字符串，字符串仅由字母“j”与字母“z”组成，描述了这个序列。

【输出格式】

　　输出文件welcome.out仅包括一个非负整数，为调整最多K次后最后最多能出现多少个“jz”子串。

【样例输入】

　　5 2

zzzjj

【样例输出】

【样例说明】

第1次交换位置1上的z和位置4上的j，变为jzzzj；

第2次交换位置4上的z和位置5上的j，变为jzzjz。

最后的串有2个“jz”子串。

【数据规模】

对于10%的数据，有N≤10；

对于30%的数据，有K≤10；

对于40%的数据，有N≤50；

对于100%的数据，有N≤500，K≤100

转载地址：http://adjbo.baihongyu.com/

你可能感兴趣的文章