ようやくVolume 5が全部埋まりました。まだ増えるだろうけど、せいぜい８個。
0508
枝かりゲーだと思っていたら枝かりの必要すらなかった。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int>g[100]; int used[100]; int solve(int a){ used[a]=1; int ret=1; for(int i=0;i<g[a].size();i++){ if(!used[g[a][i]]){ ret=max(ret,1+solve(g[a][i])); } } used[a]=0; return ret; } int main(){ int a; while(scanf("%d",&a),a){ for(int i=0;i<100;i++)g[i].clear(); for(int i=0;i<a;i++){ int b,c; scanf("%d%d",&b,&c); b--;c--; g[b].push_back(c); g[c].push_back(b); } int ret=0; for(int i=0;i<100;i++)ret=max(ret,solve(i)); printf("%d\n",ret); } }
0548
逆から探索すると速い。これも枝かりいらなかった。
#include<stdio.h> #include<algorithm> using namespace std; int m[10][10]; int R; int C; int a,b; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; int solve(int s,int t,int u){ if(u==0){ if(s==R||t==C)return 1; else return 0; } int ret=0; for(int i=0;i<4;i++){ int row=s; int col=t; while(1){ row+=dx[i]; col+=dy[i]; if(row<0||col<0||row>=a||col>=b)break; if(m[row][col]==1){ m[row][col]=3; ret+=solve(row,col,u-1); m[row][col]=1; break; } } } return ret; } int main(){ while(scanf("%d%d",&b,&a),a){ int c=0; for(int i=0;i<a;i++) for(int j=0;j<b;j++){ scanf("%d",&m[i][j]); if(m[i][j]==1)c++; if(m[i][j]==2){R=i;C=j;} } printf("%d\n",solve(R,C,c)); } }
0581
のDP。配列の次元だけ増えるつまらない問題。
#include<stdio.h> #include<algorithm> using namespace std; int dp[50][50][1<<12][4]; char str[50][51]; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++)scanf("%s",str[i]); for(int i=0;i<a;i++) for(int j=0;j<b;j++) if(str[i][j]=='.')str[i][j]='0'; for(int i=0;i<a;i++) for(int j=0;j<b;j++) for(int k=0;k<(1<<12);k++) for(int l=0;l<4;l++) dp[i][j][k][l]=-99999999; dp[0][0][0][c]=0; for(int i=c;i>=0;i--){ for(int j=0;j<a;j++){ for(int k=0;k<b;k++){ for(int l=0;l<(1<<12);l++){ if(dp[j][k][l][i]<0)continue; int R; int W; bool ok; if(j<a-1&&str[j+1][k]!='#'){ R=0;W=0;ok=true; for(int m=0;m<6;m++){ R-=dx[(l>>(m*2))&3]; W-=dy[(l>>(m*2))&3]; if(R==1&&W==0)ok=false; } if(ok){ dp[j+1][k][(l<<2)&((1<<12)-1)][i]=max(dp[j][k][l][i]+str[j+1][k]-'0',dp[j+1][k][(l<<2)&((1<<12)-1)][i]); }else{ dp[j+1][k][(l<<2)&((1<<12)-1)][i]=max(dp[j][k][l][i],dp[j+1][k][(l<<2)&((1<<12)-1)][i]); } } if(k<b-1&&str[j][k+1]!='#'){ R=0;W=0;ok=true; for(int m=0;m<6;m++){ R-=dx[(l>>(m*2))&3]; W-=dy[(l>>(m*2))&3]; if(R==0&&W==1)ok=false; } if(ok){ dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]=max(dp[j][k][l][i]+str[j][k+1]-'0',dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]); }else{ dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]=max(dp[j][k][l][i],dp[j][k+1][((l<<2)+1)&((1<<12)-1)][i]); } } if(j&&str[j-1][k]!='#'&&i){ R=0;W=0;ok=true; for(int m=0;m<6;m++){ R-=dx[(l>>(m*2))&3]; W-=dy[(l>>(m*2))&3]; if(R==-1&&W==0)ok=false; } if(ok){ dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]=max(dp[j][k][l][i]+str[j-1][k]-'0',dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]); }else{ dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]=max(dp[j][k][l][i],dp[j-1][k][((l<<2)+2)&((1<<12)-1)][i-1]); } } if(k&&str[j][k-1]!='#'&&i){ R=0;W=0;ok=true; for(int m=0;m<6;m++){ R-=dx[(l>>(m*2))&3]; W-=dy[(l>>(m*2))&3]; if(R==0&&W==-1)ok=false; } if(ok){ dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]=max(dp[j][k][l][i]+str[j][k-1]-'0',dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]); }else{ dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]=max(dp[j][k][l][i],dp[j][k-1][((l<<2)+3)&((1<<12)-1)][i-1]); } } } } } } int ret=0; for(int i=0;i<=c;i++) for(int j=0;j<(1<<12);j++)ret=max(ret,dp[a-1][b-1][j][i]); printf("%d\n",ret); }
Volume 0とVolume 5が埋まったので、とにかく今度はICPC対策を…
