题意:(感谢@似水流年 翻译)

两个人走在路上，突然发现这条路和底下的河流有n个交点。问这条河流的流向有多少种可能(n<=16)

这一题看起来非常可怕的样子..

写个暴力冷静下..然后打个表就行..

1,暴力本身会TLE

2,我暴力写炸了好多次..

程序以#ifndef absi2011/#else/#endif为界限,一半是表一半是暴力..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#ifndef absi2011
int ans[25]={2,2,4,4,12,16,56,84,324,524,2152,3656,15704,27640,122776,221908,1011756};
int main()
{
    freopen("river.in","r",stdin);
    freopen("river.out","w",stdout);
    int n;
    scanf("%d",&n);
    printf("%d\n",ans[n]);
    return 0;
}
#else
int n;
int ans=0;
int a[25];
bool used[25];
bool inside(int a,int x,int y)
{
    if (x>y) swap(x,y);
    return ((x<a)&&(a<y));
}
bool cross(int x1,int y1,int x2,int y2)
{
    if (x1>y1) swap(x1,y1);
    if (x2>y2) swap(x2,y2);
    if (inside(x1,x2,y2)^inside(y1,x2,y2)) return true;
    return false;
}
void dfs(int x)
{
    if (x==n)
    {
        int i;
        for (i=(x-1)%2+1;i<n-1;i+=2)
        {
            if (inside(a[x-1],a[i],a[i-1])) return;
        }
        ans++;
        return;
    }
    int i;
    for (i=x%2;i<n;i+=2)
    {
        if (used[i]) continue;
        a[x]=i;
        if (x>=3)
        {
            int j;
            for (j=(x-1)%2+1;j<x;j+=2)
            {
                if (cross(a[x],a[x-1],a[j],a[j-1])) break;
            }
            if (j!=x) continue;
        }
        used[i]=true;
        dfs(x+1);
        used[i]=false;
    }
}
int main()
{
    freopen("river.in","r",stdin);
    freopen("river.out","w",stdout);
    scanf("%d",&n);
    dfs(0);
    if (n%2==0) ans*=2;
    printf("%d\n",ans*2);
    return 0;
}
#endif