首页 > 代码库 > HDU-4689 Derangement
HDU-4689 Derangement
太洗脑了；
题目意思：初始队列是1，2， 3.......n ；在打乱这个队列切保证每个数字都不在原来的位置上的情况下给出一个具有+，- 的队列；
被打乱的队列 和 原来队列 对应位置的大小的关系是那个给定的 +，- 队列；
YY： 炸一看7S，n=20；状压DP 啊 开森的写完了，TTTTTTTT；这不是逗我玩呢么，他有1000组测试样例
还是DP ！
思路：
每一位的数字有俩中分配方式 填补前面的+ 或者后面的-
但是我们的DP 一般都是线性的不可能在枚举到一位的时候，左右的状态都被处理好
所以我们选择一种处理方式
1：从前往后处理，枚举到的数字往前面的+ 的位置放，或者记录下数字的个数等到枚举位置是- 时往里放
2：从后往前 和一的刚好相反
一般会选1 这样更舒服;
对于要维护的值不难发现有 位置（pos），有多少个+号所在的位置没有确定数字（cnt[+]），剩余没有用到的数字；
对于选1 的要是枚举到的位数是 - 那么一定要找个数字把他填上 所以有下面的解法
解法1：dp [i] [j] [k] ：： 枚举到位置I 时 ；
有J 个+号位置的数字好没有确定；
还有K个数字可用；
所以很容易可以得到 当前位置是+ 的时候
（1）选择把这个数字放到前面
dp[i][j][k]+= dp[i-1][j][k]*j;
（2）选择吧这个数留下来为了填后面的减号
dp[i][j][j]+= dp[i-1][j-1][k-1];
当该位置是- 的时候
（1）选择把这个数字放到前面，并找个前面剩下数字把这个位置填补
dp[i][j][k]+= dp[i-1][j+1][k+1]*(j+1)*(k+1);
（2）选择这个数字留下来，并找个前面的剩下数字把这个位置填补
dp[i][j][k]+= dp[i-1][j][k]*j；
至此dp[n-1][0][0]是答案；
代码1
#include <cstdio>#include <string>#include <algorithm>#include <iostream>#include <cstring>using namespace std;typedef long long LL;char tmp[25];int n;LL dp[21][21][21];int main(){ while(~scanf("%s",tmp)) { n=strlen(tmp); if(tmp[0]!=‘+‘ || tmp[n-1]!=‘-‘) { puts("0"); continue; } memset(dp,0,sizeof dp); dp[0][1][1]=1; for(int i=1;i<n;i++) { if(tmp[i]==‘+‘) { for(int j=0;j<=(i+1);j++) { for(int k=0;k<=(i+1);k++) { if(i>=1) dp[i][j][k]+= dp[i-1][j][k]*j; if(i>=1&&j>=1&&k>=1) dp[i][j][j]+= dp[i-1][j-1][k-1]; } } } else { for(int j=0;j<=(i+1);j++) { for(int k=0;k<=(i+1);k++) { if(i>=1) dp[i][j][k]+= dp[i-1][j+1][k+1]*(j+1)*(k+1); if(j>=1) dp[i][j][k]+= dp[i-1][j][k]*j; } } } } cout<<dp[n-1][0][0]<<endl; } return 0;}
优化：
这个是不需要三个维度的 ：
试想当到达位置P 那么一共有P个数字被决定是
放到+，-，还是留下了 ，
对于留下的数字 和 剩下的 没有被分配数值的+号位置的数量
有着相等的关系 理由如下
（减号必须被分配）
对于位置数 有加号和减号
num[加号]+num[减号] = num[被分配的加号]+num[剩下的几号]+num[减号]=P；
对于数字 有分配和未分配
num[分配]+num[未分配]= num[被分配的几号]+num[减号]+num[未分配]=P；
所以剩下的数字和未分配的数字是相等的
所以可以省一个维度
优化
#include <cstdio>#include <algorithm>#include <cmath>#include <iostream>#include <cstring>#include <cstdlib>typedef long long LL;using namespace std;LL n;LL dp[22][22];char tmp[22];int main(){ while(scanf("%s",tmp)!=EOF) { n=strlen(tmp); if(tmp[0]==‘-‘||tmp[n-1]==‘+‘) { puts("0"); continue; } memset(dp,0,sizeof(dp)); dp[0][1]=1; for(int i=1; i<n; i++) { if(tmp[i]==‘+‘) for(int j=0; j<=(i+1); j++) { if(i>=1&&j>=1) dp[i][j]+=dp[i-1][j-1]; if(i>=1) dp[i][j]+=dp[i-1][j]*j; } else for(int j=0; j<=(i+1); j++) { if(i>=1) dp[i][j]+=dp[i-1][j+1]*(j+1)*(j+1); if(i>=1) dp[i][j] +=dp[i-1][j]*j; } } cout<<dp[n-1][0]<<endl; } return 0;}
HDU-4689 Derangement