「AOJ Problem Set from ALDS1 問25～29」の編集履歴（バックアップ）一覧に戻る
*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
ｎ項めのフィナボッチ数列を出力せよという問題。
#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();
}
}
