※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

Heaps - Maximum Heap

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_B
きちんとしたヒープを組み立てる問題。


#include<stdio.h>

const int SIZE=500005;
int heap_size;
int A[SIZE];
void maxHeapify(int *A,int i){
	int l=2*i;
 	int r=2*i+1;
	int largest;
	if(l<=heap_size && A[l]>A[i]){
		largest=l;
	}else{
 		largest=i;
	}
	if(r<=heap_size&&A[r]>A[largest]){
		largest=r;
	}
	if(largest!=i){
		int t=A[i];
		A[i]=A[largest];
		A[largest]=t;
		maxHeapify(A,largest);
	}
} 

void buildMaxHeap(int *A){
	for(int i=heap_size/2;i>0;i--)maxHeapify(A,i);
}

int main(){
	int num;
 	scanf("%d",&heap_size);
	for(int i=1;i<=heap_size;i++){
		scanf("%d",&A[i]);
	}
	buildMaxHeap(A);
	for(int i=1;i<=heap_size;i++){
 		printf(" %d",A[i]);
	}
	printf("\n");
}






Heaps - Priority Queue

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C
ヒープから優先順位付きキューを作る問題
最下層の適当な数字をとりだしヒープを入れ替えていくとlog nで優先順位付きqueueの次のデータが求まる。
よくできて切るよな。


#include<stdio.h>

const int SIZE=2000001;
int heap_size=0;
int A[SIZE];

const int ERROR=-1;
void maxHeapify(int *A,int i){
	int l=2*i;
	int r=2*i+1;
	int largest;
	if(l<=heap_size && A[l]>A[i]){
		largest=l;
	}else{
		largest=i;
	}
	if(r<=heap_size&&A[r]>A[largest]){
		largest=r;
	}
	if(largest!=i){
		int t=A[i];
		A[i]=A[largest];
 		A[largest]=t;
		maxHeapify(A,largest);
	}
}

void heapIncreaseKey(int *A,int i,int key){
	if(key<A[i]){
		return ;
	}
	A[i]=key;
	while(i>1 && A[i/2]<A[i]){
		int t=A[i];
		A[i]=A[i/2];
		A[i/2]=t;
		i=i/2;
	}
}
 
void maxHeapInsert(int *A,int key){
	heap_size++;
	A[heap_size]=ERROR;
	heapIncreaseKey(A,heap_size,key);
}

int heapExtractMax(int *A){
	if(heap_size<1){
		return ERROR;
 	}
	int max=A[1];
	A[1]=A[heap_size];
	heap_size--;
	maxHeapify(A,1);
	return max;
} 


int main(){
	int key;
	char com[10];
 	while(1){
		scanf("%s",com);
		if(com[0]=='i'){
			scanf("%d",&key);
			maxHeapInsert(A,key);
		}else if(com[1]=='x'){
			int max=heapExtractMax(A);
			if(max!=ERROR)printf("%d\n",max);
		}else{
 			break;
		}
	}
}


Dynamic Programming - Fibonacci Number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A
n項めのフィナボッチ数列を出力せよという問題。


#include<stdio.h>
int main(){
	int f[50];
	f[0]=f[1]=1;
	for(int i=2;i<=44;i++)f[i]=f[i-1]+f[i-2];
	int n;
	scanf("%d",&n);
	printf("%d\n",f[n]);
}





Dynamic Programming - Matrix Chain Multiplication

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B
行列演算のスカラー積を最小にして計算した時の計算回数をこたえる問題。
解法
直列に並んだグラフとみればワーシャルフロイド法もどきが適用でき、あとはその時のスカラー積の回数に注意して計算式を立てるだけです。
計算量はn=100でも166500回。
まあこんなもんかな。


#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>

const int LIMIT=101;
long long int myMin(long long int a,long long int b){
 	if(a==0)return b;
	if(a<b) return a;
	else    return b;
}

int main(){
	int n,rs[LIMIT],cs[LIMIT],now=0,next=1;
 	long long int memo[2][LIMIT][LIMIT];
	memset(memo,0,sizeof(memo));
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d %d",&rs[i],&cs[i]);
	int count=0;
	for(int len=1;len<=n;len++){
		for(int p=0;p+len<n;p++){
			int r=p+len;
 			for(int m=p;m<r;m++){
				long long int perm=memo[now][p][m]+memo[now][m+1][r];
				perm+=rs[p]*cs[m]*cs[p+len];
				memo[next][p][r]=myMin(memo[next][p][r],perm);
				count++;
			}
		}
 		memcpy(memo[now],memo[next],sizeof(memo[now]));
	}
	std::cout<<memo[now][0][n-1]<<"\n";
}




Dynamic Programming - Longest Common Subsequence

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
最長一致部分文字列の長さをこたえる問題。
memcpyがもったいない感じはするな。

#include<stdio.h>
#include<string.h>
#include<algorithm>

const int LIMIT=1001;
int dp[2][LIMIT];
 
void search(){
char x[LIMIT],y[LIMIT];
	memset(dp,0,sizeof(dp));
	scanf("%s %s",x,y);
	int lenA=strlen(x),lenB=strlen(y),ans=0;
	const int now=0;
 	const int next=1;
	for(int i=0;i<lenA;i++){
		int max=0;
		for(int j=0;j<lenB;j++){
			if(j>0)max=std::max(max,dp[now][j-1]);
			dp[next][j]=std::max(dp[now][j],max+(x[i]==y[j]));
		}
		memcpy(dp[now],dp[next],sizeof(dp[now]));
 		memset(dp[next],0,sizeof(dp[next]));
	}
	for(int i=0;i<lenB;i++)ans=std::max(ans,dp[now][i]);
	printf("%d\n",ans);
}

int main(){
	int n;
 	scanf("%d",&n);
	while(n--){
		search();
	}
 }