1002-Extraordinary Girl (I)
少女が全ての本を棚に片づけるのにかかる最小の時間を求める問題。
最初はC++で優先度つきキューを用いて解答したけど、速度/メモリが微妙だったので
DPに書きなおした。
珍しくC言語で実装。
実装(C)
#include<stdio.h> #include<stdlib.h> #include<string.h> int C[2][2][3][3]={{{{0,1,2},{1,0,1},{2,1,0}},{{3,2,2},{2,1,1},{2,1,1}}},{{{1,1,2},{1,1,2},{2,2,3}},{{3,2,2},{2,2,2},{2,2,3}}}}; int D[10011][3]; int M[10011][2],n; char I[40010]="N"; #define min(a,b) (a)>(b)?(b):(a) int main(i,j) { for(scanf("%d",&n);~scanf("%d",&n);){ scanf("%s",I); memset(M,0,sizeof(M)); for(i=0;i<2;i++){ for(j=0;j<2*n;j++){ if(I[j+2*n*i]=='Y'){ M[(j+1)/2][i]=1; } } } memset(D,16,sizeof(D)); **D=0; for(i=0;i<=n;i++){ for(j=0;j<9;j++){ D[i+1][j%3]=min(D[i+1][j%3],D[i][j/3]+C[M[i][0]][M[i][1]][j/3][j%3]+1); } } printf("%d\n",D[i][0]-1); } return 0; }