历经千百爆零

总算苟上了200

多亏题水，痛失AK

T1：随便贪心即可。解封之后，栈里可能连续弹出要注意。

T2：

 

 

区间dp既视感

直接dp答案不好搞，最优子结构基本没有。。

考虑求cos[l][r]表示删掉l,r花费，

枚举用哪个删

因为一段一段，所以，还要考虑留下的前缀

g[l][r][id][len]，[l,r]开始，删到留下第id个串前len位的最小花费

愉快dp

cos完了后，f[i][j]前i位，删了j次留下的最小长度

O(n^3*m*len)必须剪枝

发现，cos[l][r]很大程度上是inf，或者比k大，

所以g的转移的时候，把cos循环到外面，如果cos[s+1][j]大于k-1，直接continue

稳稳AC

#include
      
       #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=202;const int inf=0x3f3f3f3f;int n,m,k;char a[N];char b[N][N];int f[N][N];int len[N];namespace sol1{int nxt[N];void main(){    int ans=n;    for(reg i=1;i<=m;++i){        int l=strlen(b[i]+1);        for(reg j=1;j<=n-l+1;++j){            int p=j,t=1;            while(t<=l&&b[i][t]==a[p]) ++t,++p;            if(t>l) ans=min(ans,n-l);        }    }    printf("%d",ans);}}namespace sol2{int cos[N][N];int g[N][N][22][13];void main(){    memset(cos,inf,sizeof cos);    memset(g,inf,sizeof g);    for(reg i=1;i<=n;++i){        for(reg j=1;j<=m;++j){            if(len[j]==1&&b[j][1]==a[i]) {                cos[i][i]=1;                g[i][i][j][len[j]]=0;                g[i][i][j][0]=1;            }            if(b[j][1]==a[i]){                g[i][i][j][1]=0;            }        }        cos[i][i-1]=0;    }cos[n+1][n]=0;    for(reg i=1;i<=n;++i){        for(reg p=1;p<=m;++p){            g[i][i-1][p][0]=0;        }    }    //cout<<" seee "<
       
        n) break;            for(reg s=i;s<=j;++s){                cos[i][j]=min(cos[i][j],cos[i][s]+cos[s+1][j]);            }            for(reg p=1;p<=m;++p)g[i][i-1][p][0]=0;            for(reg s=i-1;s
        
         k-1) continue;                for(reg p=1;p<=m;++p){                    //                    for(reg o=0;o<=len[p];++o){                                                g[i][j][p][o]=g[i][j][p][o]>g[i][s][p][o]+cos[s+1][j]?g[i][s][p][o]+cos[s+1][j]:g[i][j][p][o];                                                if(o>=1&&b[p][o]==a[j])  g[i][j][p][o]=min(g[i][j][p][o],g[i][j-1][p][o-1]);                    }                    //cos[i][j]=min(cos[i][j],g[i][j][p][len[p]]+1);                    }            }            for(reg p=1;p<=m;++p){                cos[i][j]=min(cos[i][j],g[i][j][p][len[p]]+1);                }        }    }//    for(reg l=1;l<=n;++l){//        for(reg i=1;i<=n;++i){//            int j=i+l-1;//            if(j>n) break;//            cout<<" i j "<
         <<" "<
          
           <<" : "<
           
            <
            
             0){ for(reg p=0;p
            
           
          
        
       
      

本来思路和正解一毛一样

但是以为没有优化空间

g数组每次暴力求的，，其实记录一下用[l,r]就可以少求n次，砍掉1维

然后加上剪枝即可。

以为O(n^3*m*len)过不去，，，

 

T3：

[SDOI2014]向量集

的弱化版

线段树维护凸包即可。

（可能脑残没有推出这个斜率优化的式子，，考虑点积的意义搞的右上凸包，，，当凸包斜率最接近-x/y时最大）

 

#include
      
       #define reg register int#define il inline#define mid ((l+r)>>1)#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=300000+5;int n;struct po{    int x,y;    po(){}    po(int xx,int yy){        x=xx;y=yy;    }    bool friend operator <(po a,po b){        if(a.x==b.x) return a.y
       
        =b.x)&&(a.y>=b.y);}struct node{    vector
        
         mem;}t[4*N];void upda(int x,po c){//    cout<<" udpa "<
         
          <<" : "<
          
           <<" "<
           
            <<" "<
            
             <
             
              1){ int sz=t[x].mem.size(); int tmp=cross(t[x].mem[sz-1]-c,t[x].mem[sz-2]-c); //cout<<" tmp "<
              
               <
               
                >1; if(md==0){ id=0;break; }else{ if((t[x].mem[md].y-t[x].mem[md-1].y)*c.y>=(t[x].mem[md-1].x-t[x].mem[md].x)*c.x){ id=md;ll=md+1; }else{ rr=md-1; } } } int ret=0; //cout<<" idid "<
                
                 <
                 
                  =0) ret=max(ret,dot(c,t[x].mem[id])); if(id>=1) ret=max(ret,dot(c,t[x].mem[id-1])); if(id<(int)t[x].mem.size()-1) ret=max(ret,dot(c,t[x].mem[id+1])); return ret; } int ret=0; if(L<=mid) ret=max(ret,query(x<<1,l,mid,L,R,c)); if(mid
                 
                
               
              
             
            
           
          
         
        
       
      

 

 

总结：

很悬

T2还是不够老练，，这种trick，多积累吧 。而且暴力打的不够果断。还是应该想不出来直接打暴力。差点没有时间

T3斜率优化没有推出来？害的考虑半天几何意义开始还错了。