[BZOJ 1009][HNOI2008]GT考试

好劲啊这题……

首先先想DP的做法,我们用[tex]p[i][j][/tex]表示若字符串已匹配前缀[tex][1,i][/tex],有多少种方案使得追加上一个数后匹配[tex][1,j][/tex],这个用KMP可以很方便的求出(事实上暴力也可以)

然后再来看DP的做法,转移方程大致是这样的:

[tex]d[i][j]=\Sigma_{k=0}^{m-1}(d[i-1][k]\times p[k][j])[/tex]

但是n非常大,这么做注定要TLE。

不过看这个转移方程,是不是和矩阵乘法的定义很像?是的。

我们可以用一个[tex]1\times m[/tex]的矩阵[tex]D[/tex]来表示某一个阶段的DP值,我们可以把[tex]p[/tex]组织成一个[tex]m\times m[/tex]矩阵[tex]P[/tex]。然后我们可以发现:

[tex]D_i\times P=D_{i+1}[/tex]

由于矩阵乘法满足结合律,所以:

[tex]D_n=D_0\times P^n[/tex]

很明显可以快速幂搞出来。

代码:

/**************************************************************
    Problem: 1009
    User: danihao123
    Language: C++
    Result: Accepted
    Time:80 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[22][22];
ull MOD;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))
 
inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    register int i,j,k;
    Matrix C;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,int m,ull p,Matrix& res){
    Matrix a,temp;
    register int i;
    CL_ARR(a,0);
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    REP(i,m){
        temp[i][i]=1;
    }
    while(p){
        if(1&p){
            MatrixMul(temp,a,m,m,m,temp);
        }
        p>>=1;
        MatrixMul(a,a,m,m,m,a);
    }
    CP_ARR(temp,res);
}
 
char buf[25];
int f[25];
int main(){
    register int i,u,j;
    register ull ret=0;
    ull n;
    int m;
    Matrix ans,P;
    scanf("%llu%d%llu",&n,&m,&MOD);
    scanf("%s",buf+1);
    CL_ARR(ans,0);
    ans[0][0]=1;
    CL_ARR(P,0);
    P[0][0]=9;P[0][1]=1;
    // f[0]=f[1]=0;
    for(i=1;i<m;i++){
        u=f[i];
        while(u && buf[u+1]!=buf[i+1]){
            u=f[u];
        }
        if(buf[u+1]==buf[i+1]){
            f[i+1]=u+1;
        }else{
            f[i+1]=0;
        }
        for(j=0;j<10;j++){
            u=i;
            while(u && buf[u+1]!=j+'0'){
                u=f[u];
            }
            if(buf[u+1]==j+'0'){
                P[i][u+1]=(P[i][u+1]+1)%MOD;
            }else{
                P[i][0]=(P[i][0]+1)%MOD;
            }
        }
    }
    MatrixPow(P,m,n,P);
    MatrixMul(ans,P,1,m,m,ans);
    for(i=0;i<m;i++){
        ret=(ret+ans[0][i])%MOD;
    }
    printf("%llu\n",ret);
    return 0;
}

[CodeVS 3729]飞扬的小鸟

论如何把一个完全背包出的高大上……

这个题啊……细节特别多……

首先,不建议开滚动数组,细节处理就会疯。

然后呢……真的不太好说了……还是看代码吧(尽管代码还是有明显的滚动数组痕迹)。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=1005;
const int INF=0x7f7f7f7f;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)

int GZ[maxn][2];
bool haveGZ[maxn];
int A[maxn][2];
int d[maxn][maxm];
int main(){
    int n,m,k,temp;
    register int i,j,v,now,pre,ans=INF,cnt;
    scanf("%d%d%d",&n,&m,&k);
    cnt=k;
    REP(i,n){
        scanf("%d%d",&A[i][0],&A[i][1]);
    }
    for(i=0;i<=n;i++){
        GZ[i][0]=0;
        GZ[i][1]=m+1;
    }
    REP_B(i,k){
        scanf("%d",&temp);
        haveGZ[temp]=true;
        scanf("%d%d",&GZ[temp][0],&GZ[temp][1]);
    }
    memset(d,0x7f,sizeof(d));
    memset(d[0],0,sizeof(d[0]));
    d[0][0]=INF;
    REP_B(i,n){
        now=i;
        pre=i-1;
        d[now][0]=INF;
        int& X=A[i-1][0];
        int& Y=A[i-1][1];
        REP_B(j,m){
            if(j-X>0 && d[pre][j-X]<INF)
                d[now][j]=min(d[now][j],d[pre][j-X]+1);
            if(j-X>0 && d[now][j-X]<INF)
                d[now][j]=min(d[now][j],d[now][j-X]+1);
            if(j==m)
                for(v=j-X;v<=m;v++){
                    if(d[pre][v]<INF)
                        d[now][j]=min(d[now][j],d[pre][v]+1);
                    if(d[now][v]<INF)
                        d[now][j]=min(d[now][j],d[now][v]+1);
                }
        }
        for(j=GZ[i][0]+1;j<GZ[i][1];j++){
            if(j+Y<=m && d[pre][j+Y]<INF)
                d[now][j]=min(d[now][j],d[pre][j+Y]);
        }
        if(haveGZ[i]){
            REP_B(j,GZ[i][0])
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
            for(j=GZ[i][1];j<=m;j++)
                if(d[now][j]<INF){
                    d[now][j]=INF;
                }
        }
    }
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            ans=min(ans,d[i][j]);
        }
        if(ans<INF)
            break;
        if(haveGZ[i])
            cnt--;
    }
    if(cnt==k){
        printf("1\n%d\n",ans);
    }else{
        printf("0\n%d\n",cnt);
    }
    return 0;
}

[CodeVS 1378]选课

上古CTSC提……竟然只是树形背包DP……

树形背包DP可以使用左儿子右兄弟法进行优化。这样的话每个点只需要考虑要选不选自己,摊派给兄弟多少,摊派给儿子多少。不过至于这样为何有很大的优化效果,可以参考完全背包的优化方法进行理解。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=305;
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int lc[maxn],rb[maxn],W[maxn];
inline void Insert(int x,int y,int w){
    rb[y]=lc[x];
    lc[x]=y;
    W[y]=w;
}

int d[maxn][maxn];
int dp(int x,int k){
    if(x==-1 || k<=0)
        return 0;
    if(d[x][k]>=0)
        return d[x][k];
    int i;
    int& ans=d[x][k];
    ans=dp(rb[x],k);
    for(i=0;i<k;i++){
        ans=max(ans,W[x]+dp(lc[x],i)+dp(rb[x],k-i-1));
    }
    return ans;
}

int main(){
    register int i;
    int n,m,x,w;
    scanf("%d%d",&n,&m);
    CL_ARR(lc,-1);
    CL_ARR(rb,-1);
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&w);
        Insert(x,i,w);
    }
    CL_ARR(d,-1);
    printf("%d\n",dp(0,m+1));
    return 0;
}

[CodeVS 1154]能量项链

环状DP填坑辣……

这个就是把矩阵连乘出到了环上。很容易想到的方法是枚举断点断环成链,当成简单的矩阵连乘做,不过这样的时间复杂度为[tex]O(n^4)[/tex],有点慢。我们可以直接把序列复制一份放到原序列后面,然后当成矩阵连乘做,这样的话时间复杂度仅为[tex]O(n^3)[/tex],挺优秀的。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=205;
long long d[maxn][maxn];
long long e[maxn];
int main(){
    register int i,j,k;
    register long long temp,ans=0;
    int n;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&e[i]);
        e[i+n]=e[i];
    }
    for(j=2;j<2*n;j++)
        for(i=j-1;i>=1 && (j-i+1)<=n;i--){
            for(k=i;k<j;k++){
                temp=d[i][k]+d[k+1][j]+e[i]*e[k+1]*e[j+1];
                d[i][j]=max(d[i][j],temp);
            }
            ans=max(ans,d[i][j]);
        }
    printf("%lld\n",ans);
    return 0;
}

[UVa 10635]Prince and Princess

这个名字真有童话风味哎……

直接LCS肯定会TLE。注意每个序列都是不重复序列,所以可以将A映射到[tex][1,p+1][/tex],然后再把B映射一下(有的可能A里面没有?反正既然A里没有就和LCS没关系了),就相当于求B的LIS。LIS可以在[tex]O(nlogn)[/tex]时间内完成。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=62510;
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int B[maxn];
int Hash[maxn];
int d[maxn],g[maxn];
int main(){
    int T,n,p,q,x;
    register int i,ans,k,Case=0;
    scanf("%d",&T);
    while(T--){
        Case++;
        scanf("%d%d%d",&n,&p,&q);
        CL_ARR(Hash,0);
        for(i=1;i<=(p+1);i++){
            scanf("%d",&x);
            Hash[x]=i;
        }
        for(i=1;i<=(q+1);i++){
            scanf("%d",&x);
            B[i]=Hash[x];
        }
        CL_ARR(g,0x7f);
        ans=0;
        for(i=1;i<=(q+1);i++){
            k=lower_bound(g+1,g+2+q,B[i])-g;
            d[i]=k;
            g[k]=B[i];
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",Case,ans);
    }
    return 0;
}

[LA 3942]Remember the Word

Trie第一题……

首先,容我吐槽一下UVa这个OJ,速度特别感人(同学们可以实践一下)。

这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex],枚举其前缀查是否为单词,然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。

然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex],在前缀树中查找之,就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100,所以查找会很快辣~

代码:

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))

int n;
vector<int> AnsList;
namespace Trie{
	const int maxnode=400005;
	const int sigma_siz=26;
	int Tree[maxnode][sigma_siz];
	int val[maxnode];
	int siz;
	inline int idx(char c){
		return c-'a';
	}
	inline void InitTrie(){
		siz=0;
		val[0]=0;
		CL_ARR(Tree[0],0);
	}
	void Insert(char *s,int v){
		register int u=0,n=strlen(s);
		register int i,c;
		REP(i,n){
			c=idx(s[i]);
			if(!Tree[u][c]){
				siz++;
				Tree[u][c]=siz;
				val[siz]=0;
				CL_ARR(Tree[siz],0);
			}
			u=Tree[u][c];
		}
		val[u]=v;
	}
	void Query(char *s,int len){
		register int i,c,u=0;
		AnsList.clear();
		REP(i,len){
			if(!s[i])
				break;
			c=idx(s[i]);
			if(!Tree[u][c])
				break;
			u=Tree[u][c];
			if(val[u])
				AnsList.push_back(val[u]);
		}
	}
};

char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
	register int i,j,Case=0;
	int m;
	while(scanf("%s%d",Text,&m)==2){
		Case++;
		n=strlen(Text);
		Trie::InitTrie();
		REP_B(i,m){
			scanf("%s",buf);
			len[i]=strlen(buf);
			Trie::Insert(buf,i);
		}
		d[n]=1;
		DREP(i,n){
			d[i]=0;
			Trie::Query(Text+i,n-i);
			REP(j,AnsList.size()){
				d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
			}
		}
		printf("Case %d: %d\n",Case,d[0]);
	}
	return 0;
}

[CF 710E]Generate a String

很不错的题。

很容易想到大爆搜:每搜索一个点,预处理只插入的深度,然后限制之。之后再加一些其他的剪枝。不过估计会炸。

然后有同学就想:那个删除操作真特么棘手啊……因为这个就用不了DP了……哎

不过,删除的目的是什么?下一步干啥?再插入?那就有病了。肯定是要复制。所以说我们可以想出如下状态转移方程(i11r的TeX插件好像不能排版多行公式,所以分两部分写吧):

[tex]i[/tex]为偶数时[tex]f[i]=min(f[i-1]+x,f[i/2]+y)[/tex]

[tex]i[/tex]为奇数时[tex]f[i]=min(f[i-1]+x,f[(i+1)/2]+x+y)[/tex]

然后问题就迎刃而解了。

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e7+2;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
ll d[maxn];
int main(){
    ll n,x,y;
    cin>>n>>x>>y;
    register ll i;
    d[0]=0;
    REP(i,n+1)
        d[i]=x*i;
    REP(i,n){
        if(1&i){
            d[i]=min(d[i-1]+x,d[(i+1)/2]+x+y);
        }else{
            d[i]=min(d[i-1]+x,d[i>>1]+y);
        }
    }
    cout<<d[n]<<endl;
    return 0;
}

[VIJOS P1037]搭建双塔

很不错的题啊……

很容易想到构造三维的状态,但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态,表示用前[tex]i[/tex]块水晶,搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。

转移的时候,要考虑放到高塔上还是低塔上,以及是否会导致高低塔地位对调。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=101,maxV=2001;
int d[2][maxV];
int V[maxn];
int main(){
	int n,maxj=0;
	register int i,j,now,pre;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&V[i]);
		maxj+=V[i];
	}
	memset(d,-1,sizeof(d));
	d[0][0]=0;
	for(i=1;i<=n;i++){
		now=i%2;
		pre=1-now;
		for(j=0;j<=maxj;j++){
			if(d[pre][j]>=0)
				d[now][j]=d[pre][j];
			if(V[i]<=j){
				if(d[pre][j-V[i]]>=0){
					d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]);
				}
			}
			if(V[i]>j && d[pre][V[i]-j]>=0){
				d[now][j]=max(d[now][j],d[pre][V[i]-j]+j);
			}
			if(j+V[i]<=maxj && d[pre][j+V[i]]>=0)
				d[now][j]=max(d[now][j],d[pre][j+V[i]]);
		}
	}
	if(d[1&n][0]<=0)
		puts("Impossible");
	else
		printf("%d\n",d[1&n][0]);
	return 0;
}

[CodeVS 3269]混合背包

哎……现在才敢说真正会背包DP……

这个题可以分成三类问题分别处理,然后用一个一维数组一起递推。

0-1背包和完全背包都很简单。多重背包直接递推的话复杂度很高,可以考虑单调队列优化……然而窝太弱……不过还是用了

代码:

#include <cstdio>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;
const int maxn=201,maxv=200001;
struct DQueue{
    deque<int> D;
    queue<int> Q;
    void push(int x){
        Q.push(x);
        while(!D.empty() && x>D.back())
            D.pop_back();
        D.push_back(x);
    }
    int top(){
        return D.front();
    }
    void pop(){
        if(D.front()==Q.front())
            D.pop_front();
        Q.pop();
    }
    int size(){
        return Q.size();
    }
    void clear(){
        while(!Q.empty())
            Q.pop();
        D.clear();
    }
};
int d[maxv];
int v;
void pack(int V,int W,int c){
	register int i,j,m;
	if(c==1){
		for(i=v;i>=V;i--)
			d[i]=max(d[i],d[i-V]+W);
	}else{
		if(c==-1){
			for(i=V;i<=v;i++)
				d[i]=max(d[i],d[i-V]+W);
		}else{
			c=min(c,v/V);
			for(i=0;i<V;i++){
				m=(v-i)/V;
				DQueue Q;
				for(j=0;j<=m;j++){
					if(Q.size()==c+1)
						Q.pop();
					Q.push(d[j*V+i]-j*W);
					d[j*V+i]=Q.top()+j*W;
				}
			}
		}
	}
}
int main(){
	register int i;
	int n,x,y,z;
	scanf("%d%d",&n,&v);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		pack(x,y,z);
	}
	printf("%d\n",d[v]);
	return 0;
}

[CodeVS 1044]拦截导弹

第一问很显然是最长不升子序列,直接DP即可。

第二问咋整?暴力?网络流?

其实就是最长不降子序列。具体证明嘛……自己找吧。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=22;
int d[maxn],f[maxn];
int A[maxn];
int main(){
    int n;
    register int i,j,ans=0;
    for(n=1;;n++)
        if(scanf("%d",&A[n])!=1)
            break;
    n--;
    for(i=1;i<=n;i++){
        d[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]>=A[i])
                d[i]=max(d[i],d[j]+1);
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    ans=0;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=i-1;j>=1;j--)
            if(A[j]<=A[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}