9
12
2012
0

USACO 2.3

 

Section 2.3 DONE 2012.09.08 PROB The Longest Prefix [ANALYSIS]
DONE 2012.09.09 PROB Cow Pedigrees [ANALYSIS]
DONE 2012.09.09 PROB Zero Sum [ANALYSIS]
DONE 2012.09.09 PROB Money Systems [ANALYSIS]
DONE 2012.09.12 PROB Controlling Companies [ANALYSIS]

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


The Longest Prefix

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

如果我们用dp[l]表示长为l的前缀能否被拼接出来(true表示能,false表示不能),则状态转移方程:dp[l]=ORk ( dp[l-length(sk)] and sk等于"s[l-length(sk)+1]s[l-length(sk)+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的二叉树的放法数,我们有这样一个状态转移方程:

dp[n][k]=dp[1][k-1]*dp[n-2][k-1]
         +dp[3][k-1]*dp[n-4][k-1]
         +...
         +dp[n-2][k-1]*dp[1][k-1]
当然如果n为偶数,则不可能构成一个这种二叉树。
点击查看我的代码:
/*
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;
}
Category: USACO | Tags: usaco | Read Count: 857

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com