20160322 Code VS 1295 N 황후 문제, 1958 자극, 3113 두 갈래 나무 계수 2

1295 N 퀸 질문
#include<cstdio>
int g[20],n,cnt,vis[20];
int is_ok(int k){
    for(int i=0;i<k;i++)
        if(i-g[i]==k-g[k]||i+g[i]==k+g[k])return 0;
    return 1;
}
void dfs(int k){
    if(k==n){
        cnt++;
        return ;
    }
    for(int i=0;i<n;i++)if(!vis[i]){
        vis[i]=1;
        g[k]=i;
        if(is_ok(k))dfs(k+1);
        vis[i]=0;
    }
}
int main()
{
    scanf("%d",&n);
    dfs(0);
    printf("%d
",cnt); return 0; }

1958 자극
#include<cstdio>
#include<cmath>
int m,n,ans;
double a[101][101],all;
void dfs(int i,int j,int s,int x){
    ans=(ans>x?ans:x);
    if(s){
        if(i+1<m&&a[i+1][j]>a[i][j]&&a[i+1][j]<=all)dfs(i+1,j,!s,x+1);
        if(j+1<n&&a[i][j+1]>a[i][j]&&a[i][j+1]<=all)dfs(i,j+1,!s,x+1);
    }else{
        if(i+1<m&&a[i+1][j]<a[i][j]&&a[i+1][j]<=all)dfs(i+1,j,!s,x+1);
        if(j+1<n&&a[i][j+1]<a[i][j]&&a[i][j+1]<=all)dfs(i,j+1,!s,x+1);
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            scanf("%lf",&a[i][j]);
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++){
            all=a[i][j];
            dfs(i,j,0,1);
        }
    printf("%d
",ans); return 0; }

3113 두 갈래 나무 계수2
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct BigInteger{// 
    int A[25];
    enum{MOD = 10000};
    BigInteger(){memset(A, 0, sizeof(A)); A[0]=1;}
    void set(int x){memset(A, 0, sizeof(A)); A[0]=1; A[1]=x;}
    void print(){
        printf("%d", A[A[0]]);
        for (int i=A[0]-1; i>0; i--){
            if (A[i]==0){printf("0000"); continue;}
            for (int k=10; k*A[i]<MOD; k*=10) printf("0");
            printf("%d", A[i]);
        }
        printf("
"); } int& operator [] (int p) {return A[p];} const int& operator [] (int p) const {return A[p];} BigInteger operator + (const BigInteger& B){ BigInteger C; C[0]=max(A[0], B[0]); for (int i=1; i<=C[0]; i++) C[i]+=A[i]+B[i], C[i+1]+=C[i]/MOD, C[i]%=MOD; if (C[C[0]+1] > 0) C[0]++; return C; } BigInteger operator * (const BigInteger& B){ BigInteger C; C[0]=A[0]+B[0]; for (int i=1; i<=A[0]; i++) for (int j=1; j<=B[0]; j++){ C[i+j-1]+=A[i]*B[j], C[i+j]+=C[i+j-1]/MOD, C[i+j-1]%=MOD; } if (C[C[0]] == 0) C[0]--; return C; } }a[101]; int main() { int n; a[0].set(1);a[1].set(1);a[2].set(2); scanf("%d",&n); for(int i=3;i<=n;i++) for(int k=0;k<i;k++) a[i]=a[i]+a[k]*a[i-k-1]; a[n].print(); return 0; }

좋은 웹페이지 즐겨찾기