SRM 227 DIV1 Middle - TreeSpreading

問題

a,b,c,dの４種類の木を並べて植えたい。
ただし、隣り合う木は必ず別の種類にしたい。
それぞれの植えられる木の本数が与えられるとき、木の植え方が全部で何通りあるか求める。

解き方

ｄｐで解けそうな問題。
状態は前に植えた木、各種類の木についてあと何本植えられるかがわかればよい。
メモ化を使って全ての状態を洗い出し、最後に問題文で与えられた本数についての答えを返してあげる。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()


class TreeSpreading {

public:

long long countArrangements(int a, int b, int c, int d) {
if(a+b+c+d==0)return 1;
long long dp[4][11][11][11][11]={};

dp[0][1][0][0][0]=1;
dp[1][0][1][0][0]=1;
dp[2][0][0][1][0]=1;
dp[3][0][0][0][1]=1;

FORE(i,0,11)FORE(j,0,11)FORE(k,0,11)FORE(l,0,11)FORE(m,0,4){
if(m!=0 && i>0)dp[0][i][j][k][l]+=dp[m][i-1][j][k][l];
if(m!=1 && j>0)dp[1][i][j][k][l]+=dp[m][i][j-1][k][l];
if(m!=2 && k>0)dp[2][i][j][k][l]+=dp[m][i][j][k-1][l];
if(m!=3 && l>0)dp[3][i][j][k][l]+=dp[m][i][j][k][l-1];
}
return dp[0][a][b][c][d]+dp[1][a][b][c][d]+dp[2][a][b][c][d]+dp[3][a][b][c][d];
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()


class TreeSpreading {

public:

long long countArrangements(int a, int b, int c, int d) {
if(a+b+c+d==0)return 1;

long long dp[a+2][b+2][c+2][d+2][4];
memset(dp,0,sizeof(dp));
dp[1][0][0][0][0]=1;
dp[0][1][0][0][1]=1;
dp[0][0][1][0][2]=1;
dp[0][0][0][1][3]=1;

FORE(i,0,a+1)FORE(j,0,b+1)FORE(k,0,c+1)FORE(l,0,d+1)FORE(m,0,4){
if(m!=0)dp[i+1][j][k][l][0]+=dp[i][j][k][l][m];
if(m!=1)dp[i][j+1][k][l][1]+=dp[i][j][k][l][m];
if(m!=2)dp[i][j][k+1][l][2]+=dp[i][j][k][l][m];
if(m!=3)dp[i][j][k][l+1][3]+=dp[i][j][k][l][m];
}

return dp[a][b][c][d][0]+dp[a][b][c][d][1]+dp[a][b][c][d][2]+dp[a][b][c][d][3];
}

};

Share this

Related Posts