Baudelaire is Programmer

2.3关开始出现更多动态规划问题。

The Longest Prefix

给定一个字符串集合S={s₁,s₂,s₃...}和一个长字符串s，S中的字符串可以拼接出的s的最长前缀。

如果我们用dp[l]表示长为l的前缀能否被拼接出来（true表示能，false表示不能），则状态转移方程：dp[l]=OR_k ( dp[l-length(s_k)] and s_k等于"s[l-length(s_k)+1]s[l-length(s_k)+2]...s[l]" )，其中OR表示“或”逻辑，and表示“与”逻辑。于是我们可以边输入边动归，试验集合中每个字符串。

点击查看我的代码:

/*
ID: xxxxxxx
LANG: C++
TASK: prefix
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char str[200001];
bool dp[200000];
char set[201][11];
int len[201];
int numset;
int tail;
FILE *fin,*fout;
int max;

int main(){
	fin=fopen("prefix.in","r");
	fout=fopen("prefix.out","w");
	numset=0;
	while(fscanf(fin,"%s",set[numset]) && set[numset][0]!='.'){
		len[numset]=strlen(set[numset]);
		numset++;
	}
	char c;
	tail=-1;
	max=0;
	while((c=fgetc(fin))!=EOF){
		if(c=='\n')continue;
		str[++tail]=c;
		dp[tail]=false;
		int i;
		for(i=0;i<numset;i++){
			if(tail+1>=len[i]){
				if(tail+1>len[i] && !dp[tail-len[i]])continue;
				int j;
				for(j=0;j<len[i];j++){
					if(str[tail-(len[i]-j)+1]!=set[i][j])break;
				}
				if(j==len[i]){
					dp[tail]=true;
					if(tail+1>max)max=tail+1;
					break;
				}
			}
		}
	}
	fprintf(fout,"%d\n",max);
	return 0;
}

Cow Pedigrees

一种二叉树每个节点都有零个或两个儿子节点，用N个节点构造一个高度为K的这种二叉树一共有多少种方法？这里的高度指的是根节点到叶子节点的最多节点数。

二叉树有天然的子结构。所以如果用dp[n][k]表示n个节点构造高度为k的二叉树的放法数，我们有这样一个状态转移方程：

/*
ID: xxxxxxx
LANG: C++
TASK: nocows
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N,K;
int dp[200][100];

int main(){
	fin=fopen("nocows.in","r");
	fout=fopen("nocows.out","w");
	fscanf(fin,"%d %d",&N,&K);
	if(N%2==0){
		fprintf(fout,"%d\n",0);
		return 0;
	}
	int n,k;
	for(n=1;n<=N;n++)
		dp[n][0]=0;
	for(k=1;k<=K;k++)
		dp[1][k]=1;
	for(n=3;n<=N;n+=2)
		for(k=1;k<=K;k++){
			dp[n][k]=0;
			int i;
			for(i=1;i<=n-2;i++)
				dp[n][k]+=(dp[i][k-1]*dp[n-1-i][k-1])%9901;
			dp[n][k]%=9901;
		}
	int ans=dp[N][K]-dp[N][K-1];
	if(ans<0)
		ans+=9901;
	fprintf(fout,"%d\n",ans);
	return 0;
}

Zero Sum

在一列数1 2 3 ... N之间插入加号，减号或者空格，组合成一个算式，输出算式结果为0的那些

又是简单粗暴的枚举，dfs搜索所有情况，然后对算式求值:

/*
ID: xxxxxxx
LANG: C++
TASK: zerosum
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N;
int num[9]={1,2,3,4,5,6,7,8,9};
char sign[8];

void check(){
	int i;
	int sum=0;
	int n=1;
	int pre=1;
	for(i=0;i<=N-2;i++){
		if(sign[i]==' '){
			n=n*10+num[i+1];
		}
		else if(sign[i]=='+'){
			sum+=pre*n;
			pre=1;
			n=num[i+1];
		}
		else if(sign[i]=='-'){
			sum+=pre*n;
			pre=-1;
			n=num[i+1];
		}
	}
	sum+=pre*n;
	if(sum==0){
		fprintf(fout,"%d",num[0]);
		for(i=1;i<N;i++){
			fprintf(fout,"%c%d",sign[i-1],num[i]);
		}
		fprintf(fout,"\n");
	}
}

void dfs(int c){
	if(c==N-1){
		check();
		return;
	}
	sign[c]=' ';
	dfs(c+1);
	sign[c]='+';
	dfs(c+1);
	sign[c]='-';
	dfs(c+1);
	return;
}

int main(){
	fin=fopen("zerosum.in","r");
	fout=fopen("zerosum.out","w");
	fscanf(fin,"%d",&N);
	dfs(0);
	return 0;
}

Money Systems

用几种面值的硬币组合出一个钱数一共有多少种办法？完全背包问题，在初始化边界条件和设计状态转移方程的时候有一定技巧，详情见经典的背包九讲。我们用dp[v][n]表示前v种硬币组合出钱数n的方法数，状态转移方程：

dp[v][n]=dp[v-1][n]+dp[v][n-value(v)]

/*
ID: xxxxxxx
LANG: C++
TASK: money
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int V,N;
int value[26];
long long dp[26][10001];


int main(){
	fin=fopen("money.in","r");
	fout=fopen("money.out","w");
	fscanf(fin,"%d %d",&V,&N);
	int v,n;
	for(v=1;v<=V;v++)
		fscanf(fin,"%d",&value[v]);
	for(v=0;v<=V;v++)
		dp[v][0]=1;
	for(n=1;n<=N;n++)
		dp[0][n]=0;
	for(v=1;v<=V;v++){
		for(n=1;n<=N;n++){
			dp[v][n]=dp[v-1][n];
			if(n-value[v]>=0)
				dp[v][n]+=dp[v][n-value[v]];
		}
		printf("\n");
	}
	fprintf(fout,"%lld\n",dp[V][N]);
	return 0;
}

Controlling Companies

着实被这道题卡了不少时间，实际上不用考虑太多，一个二维表表示公司之间控股情况，不断借助可控的公司更新这个表，直到这个表不在变化，就表示我们得到了最终的结果。我认为这个题没有什么可以发掘的，想多了反而容易钻牛角尖。

/*
ID: xxxxxxx
LANG: C++
TASK: concom
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N;
int control[101][101];
int count[101][101];
bool done[101][101];

int main(){
        fin=fopen("concom.in","r");
        fout=fopen("concom.out","w");
        fscanf(fin,"%d",&N);
        int i,j,p;
        while(N){
                fscanf(fin,"%d %d %d",&i,&j,&p);
                count[i][j]=control[i][j]=p;
                N--;
        }
        for(i=1;i<=100;i++){
                while(1){
                        bool change=false;
                        for(j=1;j<=100;j++){
                                if(count[i][j]>50&&!done[i][j]){
                                        done[i][j]=true;
                                        change=true;
                                        for(p=1;p<=100;p++)
                                                if(i!=p)
                                                        count[i][p]+=control[j][p];
                                }
                        }
                        if(!change)break;
                }
        }
        for(i=1;i<=100;i++)
                for(j=1;j<=100;j++)
                        if(i!=j&&count[i][j]>50)
                                fprintf(fout,"%d %d\n",i,j);
        return 0;
}