时间限制：1s
内存限制：256MB
【问题描述】
对于一个1～n的排列，如果满足第i个数|ai-i|<=k，则称该排列为K-近似排列。
现在排列的若干位置已经确定，你需要计算剩下的数有多少种排列方法使得形成的排列是K-近似排列。
【输入】
输入文件名为count.in。
第一行一个数T(<=10)，表示数据组数
对于每一组数据：
第一行三个数n，m，k，分别表示排列长度、已确定位置的个数和近似参数K
接下来m行，每行两个数x、y，表示已经确定第x个数是y
【输出】
输出文件名为count.out。
对于每组数据输出一行，包含一个数，表示方法个数（对1,000,000,007取模）
【输入输出样例】
|
count.in |
count.out |
|
1 4 1 1 2 3 |
1 |
【数据说明】
对于30%的数据，1<=n，m<=10,k<=2
对于50%的数据，1<=n,m<=20,k<=2
对于70%的数据，1<=n<=100000,m<=100,k<=2
对于100%的数据，1<=n<=10^9,m<=100,k<=2
坑啊，题目给的样例不对，他写的是2，其实是1.！
小暴力50分
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<cstring> #include<cmath> using namespace std; int n,m,k,t; int a[100009]; bool vis[100009]; long long ans; void dfs(int x) { if(x==n+1) { ans++; return ; } if(a[x]) dfs(x+1); else { if(x>=3) if(!vis[x-k]) { vis[x-k]=1; dfs(x+1); vis[x-k]=0; return ; } for(int i=max(x-k,1);i<=min(x+k,n);i++) if(!vis[i]) { vis[i]=1; dfs(x+1); vis[i]=0; } } return ; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) a[i]=0,vis[i]=0; ans=0; for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); a[x]=y;vis[y]=1; } dfs(1); printf("%lld ",ans); } return 0; }
也可以用状压dp做
定义f[j]为当前位上状态为j的方案数，j是一个二进制数，对一每一位上1代表这个数用过，0代表没用过。（其实能用二维的，习惯用一维，有个二维代码）
对于每个状态，看看能否和 i-k到i+k中每个数拓展，，能拓展的话，就向更大的数扩展。（就是说看看这些数选没选，没选过的话就加过去）。
70分还是没写出来。。。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int P=1000000007; int f[1<<20],a[100009]; int t,n,m,k; int main() { scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); memset(a,-1,sizeof(a)); while(m--) { int x,y; scanf("%d%d",&x,&y); x--,y--; a[x]=y; } memset(f,0,sizeof(f)); for(int i=0;i<=k&&i<n;i++) { if(a[0]!=-1&&a[0]!=i) continue; f[1<<i]=1; } for(int i=0;i<n-1;i++) for(int j=(1<<n)-1;j>=0;j--) { if(!f[j]) continue; for(int t=max(0,i+1-k);t<=min(n-1,i+1+k);t++) { if(j>>t&1) continue; if(a[i+1]!=-1&&a[i+1]!=t) continue; f[j|(1<<t)]=(f[j|(1<<t)]+f[j])%P; } } printf("%d ",f[(1<<n)-1]); } return 0; }
50分DP
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int P=1000000007; int f[20][1<<20],a[20]; int t,n,m,k; int main() { scanf("%d",&t); while(t--) { scanf("%d%d%d",&n,&m,&k); memset(a,-1,sizeof(a)); while(m--) { int x,y; scanf("%d%d",&x,&y); x--,y--; a[x]=y; } memset(f,0,sizeof(f)); for(int i=0;i<=k&&i<n;i++) { if(a[0]!=-1&&a[0]!=i) continue; f[0][1<<i]=1; } for(int i=0;i<n-1;i++) for(int j=0;j<(1<<n);j++) { if(!f[i][j]) continue; for(int t=max(0,i+1-k);t<=min(n-1,i+1+k);t++) { if(j>>t&1) continue; if(a[i+1]!=-1&&a[i+1]!=t) continue; if(abs(t-(i+1))>k) continue; f[i+1][j|(1<<t)]=(f[i+1][j|(1<<t)]+f[i][j])%P; } } printf("%d ",f[n-1][(1<<n)-1]); } return 0; }