2018年3月

#include <iostream>
using namespace std;
#define MAXINT 0x7FFFFFFF
#define maxn 110
int f[maxn][maxn];
int w[maxn]; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
    int i,j,k,n;
    cin >> n;
    for(i = 1;i<=n;++i){
        for(j = 1; j<=n;++j){
            f[i][j] = MAXINT;
        }
    }
    for(i=1;i<=n;++i){
        cin>>w[i];
    }
    for(i=1;i<=n;++i){
        f[i][i-1]=f[i][i] = f[i][i+1] = 0;//初始化 
    }
    for(i=2;i<n;++i){
        f[i-1][i+1] = w[i-1]*w[i]*w[i+1];//保存每个相隔的数字相乘 
    }
    for(i=n-2;i>0;--i){
        for(j=i+2;j<=n;++j){
            for(k=i+1;k<j;++k){
                if(f[i][j]>f[i][k]+w[i]*w[k]*w[j]+f[k][j]){
                    f[i][j] = f[i][k]+w[i]*w[k]*w[j]+f[k][j];//如果这种排法比上次更小则记录 
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
int n,total=0;
int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
void print(){
    for(int i = 0;i<n;i++){
        cout<<a[i];
    }
    cout<<"\n";
    total++;
} 

int main(int argc, char** argv) {
    cin>>n;
    print();
    while(next_permutation(a,a+n)){//提供开始指针结束指针
        print();//输出
    }
    cout<<total<<'\n';
    return 0;
}

#include <iostream>
using namespace std;
int N,a[33],full,bitmod[39],amount; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void print(){
    for(int i = 1;i<N;++i){
        cout<<a[i];
    }
    cout<<a[N]<<'\n';
}

void dfs(int dep,int layout){
    if(layout == full){//判断满了没
        print();
        ++amount;
    }else{
        int p,CanPut = (~layout)&full;//判断是否有可以插入 通过layout取反跟Full&比
        while(CanPut){
            p=CanPut&(-CanPut);//取右边第一个数
            CanPut-=p;
            a[dep] = bitmod[p%37];
            dfs(dep+1,layout+p);//继续深入
        }
    }
}
int main(int argc, char** argv) {
    cin>>N;
    for(int i = 0;i<N;++i){
        bitmod[(1<<i)%37]=i+1;//哈希表 键位为37取余
    }
    full = (1<<N)-1;//1<<N -1 则0111111 为满
    dfs(1,0);//第一层开始
    cout<<amount<<'\n';
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstdlib> 
using namespace std;
bool used[100];
int a[100],Count,N;

void print(){
    for(int k = 1;k<N+1;k++){
        cout<<a[k];
    }
    cout << "\n";
    Count++;
}

void dfs(int i){
    if(i>N){
        print();
    }else{
        for(int k = 1;k<=N;k++){
            if(used[k] == 0){
                used[k] = 1;
                a[i] = k;
                dfs(i+1);
                used[k] = 0;
            }
        }
    }
}

int main(int argc, char** argv) {
    int j;
    cin>>N;
    dfs(1);
    cout<<Count<<endl;
    return 0;
}