3297. 铺瓷砖

题面 统计数据 讨论
umrwww
5 年，7 月前 
#include <stdio.h>
#include <iostream>
#include <algorithm> 
#include <string>

using namespace std;
//nowN 当前长度；one 长度为1的瓷砖块数；
int cnt_ans = 0; //方案数 
int cnt_one = 0;  

void DFS(int n, int nowN, int one, int pre, int now){   
    if(nowN > n || pre==now) return;
    if(nowN==n){
        cnt_ans++;
        cnt_one += one;
    }
    //决策1：选1 
    DFS(n, nowN+1, one+1, now, 1);
    //决策2：选2
    DFS(n, nowN+2, one, now, 2);
    //决策3：选3
    DFS(n, nowN+3, one, now, 3); 
}


int main(){

    int T;
    scanf("%d", &T);
    while(T--){
        int n; //地板总长度 
        scanf("%d", &n);

        cnt_ans = 0;
        cnt_one = 0;
        DFS(n, 0, 0, -1, 0);
        printf("%d\n%d\n", cnt_ans, cnt_one);
    } 

    return 0;

}
回复
cd106224
4 年，1 月前

DP

//状态：拼成前i段距离时，最后一个长度为j的最多拼法为dp[i][j]
#include <iostream>
#include <algorithm>
using namespace std;
int dp[31][4];
int dp1[31][4];
int n;
int main() {
    int num;
    cin >> num;
    while (num--) {
        cin >> n;
        fill(dp[0], dp[0] + 31 * 4, 0);
        fill(dp1[0], dp1[0] + 31 * 4, 0);
        for (int i = 1; i <= 3; ++i) {
            dp[i][i] = 1;
        }
        dp1[1][1] = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 1; j <= 3; ++j) {
                    for (int k = 1; k <= 3; ++k) {
                        if (j == k) {
                            continue;
                        }
                        dp[i][j] = dp[i][j] + dp[i - j][k];
                        dp1[i][j] = dp1[i][j] + dp1[i - j][k];
                        if (j == 1) {
                            dp1[i][j] += dp[i - j][k];
                        }
                    }
            }
        }
        int ans = 0;
        ans = dp[n][1] + dp[n][2] + dp[n][3];
        cout << ans << endl;
        int ans1 = 0;
        ans1 = dp1[n][1] + dp1[n][2] + dp1[n][3];
        cout << ans1 << endl;
    }
    return 0;
}
回复
小摸不算摸
2 年，4 月前

include

//前三个是不同长度下最大方法，后三个是不同长度下1的个数
int dp[30][6]={{1,0,0,1,0,0},{0,1,0,0,0,0},{1,1,1,1,1,0}};
int main()
{
int T;scanf(“%d”,&T);
for(int i =3;i<30;i++)
{
dp[i][0]=dp[i-1][1]+dp[i-1][2];
dp[i][1]=dp[i-2][0]+dp[i-2][2];
dp[i][2]=dp[i-3][0]+dp[i-3][1];
dp[i][3]=dp[i-1][4]+dp[i-1][5]+dp[i][0];
dp[i][4]=dp[i-2][3]+dp[i-2][5];
dp[i][5]=dp[i-3][3]+dp[i-3][4];
}
for(int num=0;num<T;num++)
{
int N;scanf(“%d”,&N);
int ways=dp[N-1][0]+dp[N-1][1]+dp[N-1][2];
int number=dp[N-1][3]+dp[N-1][4]+dp[N-1][5];
printf(“%d\n%d\n”,ways,number);
}
return 0;
}

回复
WhiteLi
4 年，2 月前

直接暴搜都能过。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[31];
int dp1[31];
void dfs(int now,int a,int b,int c,int n,int last)
{
    if (now>n) return;
    if (now==n)
    {
        dp1[n]+=a;
        dp[n]++;
    }
    if (last!=1) dfs(now+1,a+1,b,c,n,1);
    if (last!=2) dfs(now+2,a,b+1,c,n,2);
    if (last!=3) dfs(now+3,a,b,c+1,n,3);
}
int main()
{
    for (int i=1;i<=30;i++) dfs(0,0,0,0,i,-1);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<dp[n]<<endl<<dp1[n]<<endl;    
    }   
    return 0;
}
回复
Xiba
5 年，9 月前

include

using namespace std;
int number;
int t;
int N[31];
void cl()
{
for(int i=1;i<=30;i++)
{
N[i]=0;
}
}
void f(int k,int n,int depth)
{
int d=depth+1;
if(n<0)
{
return;
}
if(n==0)
{
number++;
for(int i=1;i<=depth;i++)
{
if(N[i]==1)
t++;
}
return;
}
if(k==0)
{
N[d]=1;
f(1,n-1,d);
N[d]=2;
f(2,n-2,d);
N[d]=3;
f(3,n-3,d);
}
if(k==1)
{
N[d]=2;
f(2,n-2,d);
N[d]=3;
f(3,n-3,d);
}
if(k==2)
{
N[d]=1;
f(1,n-1,d);
N[d]=3;
f(3,n-3,d);
}
if(k==3)
{
N[d]=1;
f(1,n-1,d);
N[d]=2;
f(2,n-2,d);
}
}
int main()
{
int T;
int n;
cin>>T;
for(int i=0;i>n;
number=0;
t=0;
cl();
f(0,n,0);
cout<<number<<endl;
cout<<t<<endl;
}
return 0;
}

回复
liningx
3 年，1 月前 
#include<bits/stdc++.h>
using namespace std;
int t, n, dp[31][4][2];
int yu[][2] = {{0,0},{2,3},{1,3},{1,2}};
int main(){
    cin >> t;
    while(t--){
        cin >> n;
        memset(dp,0,sizeof dp);
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= 3; ++j){
                if(i - j == 0){
                    dp[i][j][0] = 1;
                    dp[i][j][1] = (j==1) ? 1 : 0;
                }
                else if(i > j){
                    dp[i][j][0] = dp[i-j][yu[j][0]][0] + dp[i-j][yu[j][1]][0];
                    if(j == 1){
                        if(dp[i-1][2][0])
                            dp[i][1][1] += dp[i-1][2][0] + dp[i-1][2][1];
                        if(dp[i-1][3][0])
                            dp[i][1][1] += dp[i-1][3][0] + dp[i-1][3][1];
                    }
                    else 
                        dp[i][j][1] += dp[i-j][yu[j][0]][1] + dp[i-j][yu[j][1]][1];
                }

            }
            //printf("%d %d %d \n", dp[i][1][1],dp[i][2][1],dp[i][3][1]); 
        }
        cout << dp[n][1][0] + dp[n][2][0] + dp[n][3][0] << endl;
        cout << dp[n][1][1] + dp[n][2][1] + dp[n][3][1] << endl;
    }
}
回复
cd106224
4 年，1 月前

DFS

#include <iostream>
using namespace std;
int n;
int ans;
int res_1;
int res_2;
void DFS(int sum, int res, int res_1) {
    if (sum > n) {
        return;
    }
    if (sum == n) {
        ans++;
        res_2 += res_1;
        return;

    }
    if (res == 0) {
        DFS(sum + 1, 1, res_1 + 1);
        DFS(sum + 2, 2, res_1);
        DFS(sum + 3, 3, res_1);

    }
    else if (res == 1) {
        DFS(sum + 2, 2, res_1);
        DFS(sum + 3, 3, res_1);
    }
    else if (res == 2) {
        DFS(sum + 1, 1, res_1 + 1);
        DFS(sum + 3, 3, res_1);
    }
    else if (res == 3) {
        DFS(sum + 1, 1, res_1 + 1);
        DFS(sum + 2, 2, res_1);
    }
}


int main() {
    int num;
    cin >> num;
    while (num--) {
        cin >> n;
        ans = 0;
        res_1 = 0;
        res_2 = 0;
        DFS(0, 0, 0);
        cout << ans << endl;
        cout << res_2 << endl;
    }
    return 0;
}
回复
KyrieL
4 年，9 月前 
#include <bits/stdc++.h>
using namespace std;
#define FOR0(a,b) for(int i = a; i < b; ++i)
#define FORE(a,b) for(int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int,int> pii;
const int f[] = {1,2,3};
int ans = 0, yi = 0, n;
void dfs(int sum, int pre, int fir) {
    if(sum > n) return;
    if(sum == n) {
        // cout << yi << endl;
        ans++;
        yi+=fir;
        return;
    }
    for(int i = 0; i < 3; ++i)  {
        if(f[i] == pre) continue;
        dfs(sum+f[i],f[i],fir+(f[i]==1));
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        ans = 0, yi = 0;     
        scanf("%d", &n);
        dfs(0,0,0);
        cout << ans << endl << yi << endl;
    }
    return 0;
}
回复
KyrieL
4 年，9 月前

include

using namespace std;

define FOR0(a,b) for(int i = a; i < b; ++i)

define FORE(a,b) for(int i = a; i <= b; ++i)

typedef long long ll;
typedef pair pii;
const int f[] = {1,2,3};
int ans = 0, yi = 0, n;
void dfs(int sum, int pre, int fir) {
if(sum > n) return;
if(sum == n) {
// cout << yi << endl;
ans++;
yi+=fir;
return;
}
for(int i = 0; i < 3; ++i) {
if(f[i] == pre) continue;
dfs(sum+f[i],f[i],fir+(f[i]==1));
}
}
int main() {
int T;
scanf(“%d”, &T);
while(T–) {
ans = 0, yi = 0;
scanf(“%d”, &n);
dfs(0,0,0);
cout << ans << endl << yi << endl;
}
return 0;
}

回复
clysto
3 年，9 月前 
#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    int dp[100];
    int dp1[100][4];
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 3;
    dp1[1][1] = 1;
    dp1[1][2] = 0;
    dp1[1][3] = 0;

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

    dp1[3][1] = 1;
    dp1[3][2] = 1;
    dp1[3][3] = 1;

    int dp3[100][4];


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

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

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

    while (T--) {
        int N;
        cin >> N;
        for (int i = 4; i <= N; i++) {
            dp[i] = dp[i - 3] - dp1[i - 3][3] + dp[i - 2] - dp1[i - 2][2] + dp[i - 1] - dp1[i - 1][1];
            dp1[i][1] = dp[i - 1] - dp1[i - 1][1];
            dp1[i][2] = dp[i - 2] - dp1[i - 2][2];
            dp1[i][3] = dp[i - 3] - dp1[i - 3][3];

            dp3[i][1] = dp3[i - 1][2] + dp3[i - 1][3] + dp1[i][1];
            dp3[i][2] = dp3[i - 2][1] + dp3[i - 2][3];
            dp3[i][3] = dp3[i - 3][1] + dp3[i - 3][2];;
        }
        cout << dp[N] << endl;
        cout << dp3[N][1] + dp3[N][2] + dp3[N][3] << endl;
    }

    return 0;
}
回复
你当前正在回复 博客/题目
存在问题！

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn