1296 有限制的排列
题目简洁,不解释.
这个题目在转移的时候用到一个特点:
假定长为len的一个排列 其中的元素只有1->len, 即每个元素各一个, dp[len] [endval] 表示len长度的排列, 其中以endval作为结尾的排列数量. 当它已知时候, dp[len+1] [endval1]可以理解为从上方已知的dp[len] [endval] 的所有排列中, 对值大于等于endval1的元素都把值加上1, 其他的值不变,那么endval1元素顺利成章的放在 <最后> 作为len+1的排列的结尾 . 这么做不会改变dp[len] [endval]这个中所有排列对于题目中限定满足, 因为题目的限定条件说白了就是规定了元素之间的大小关系, 与具体的值并无关联, 那么如果对于阈值以及以上的所有元素都加1并不会改变各个位置的元素之间的大小关系. 所以在转移的时候只需要考虑我当前的endval1和前面转移过来的endval是不是满足在下标为 len, len+1 两个地方的限定条件就行了.
那么这里做的方法就是我们想象开一个二维数组, 比如sum[len] [endval]表示dp[len] [1]->dp[len] [len] 的总和,那么根据len和len+1的两个位置的限定可以 确定当len+1排列的最末尾值为endval1时,len排列的最末尾的值要比endval1小/大/无限制, 因此这样可以根据前缀和即sum顺利完成计算.
这个题很奇怪, 我这里只能开下一个n*n的二维数组, 否则超内存, 所以在计算完dp的每一位置的值之后马上可以转化为sum, 因为每一个dp的值只会被用来算sum并且只会被使用一次, 所以不如直接转化其含义,节省空间
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e3 + 60; const int mod = 1e9 + 7; int dp[maxn][maxn]; int saveori[maxn]; void solve(){ int n, an, bn; cin>>n>>an>>bn; for(int i = 1;i<=an;i++){ int v; scanf("%d", &v); v++; saveori[v] = -1; } for(int j = 1;j<=bn;j++){ int v; scanf("%d", &v); v++; saveori[v] = 1; } dp[1][1] = 1; for(int len =2;len<=n;len++){ for(int endval = 1;endval <= len;endval++){ if(saveori[len] == 0 && saveori[len - 1] == 0){ dp[len][endval] = dp[len - 1][len - 1]; } //左边大 if(saveori[len] ==0 && saveori[len - 1] == 1){ dp[len][endval] = (dp[len-1][len - 1] - dp[len-1][endval - 1]); } //左边小 if(saveori[len] == 0 && saveori[len-1] == -1){ dp[len][endval] = dp[len-1][endval - 1]; } //左边小 if(saveori[len] == 1 && saveori[len - 1] == 0){ dp[len][endval] = dp[len - 1][endval - 1]; } //没有 if(saveori[len] == 1 && saveori[len - 1] == 1){ dp[len][endval] = 0; } //左边小 if(saveori[len] == 1 && saveori[len-1] == -1){ dp[len][endval] = dp[len-1][endval - 1]; } //左边大 if(saveori[len] == -1 && saveori[len - 1] == 0){ dp[len][endval] = (dp[len-1][len - 1] - dp[len-1][endval - 1]); } //左边大 if(saveori[len] == -1 && saveori[len - 1] == 1){ dp[len][endval] = (dp[len-1][len - 1] - dp[len-1][endval - 1]); } if(saveori[len] == -1 && saveori[len - 1] == -1){ dp[len][endval] = 0; } if(dp[len][endval] < 0){ dp[len][endval]%=mod; dp[len][endval]+=mod; dp[len][endval]%=mod; } dp[len][endval] = dp[len][endval-1] + dp[len][endval]; dp[len][endval]%=mod; } } cout<<dp[n][n]<<endl; } signed main(){ //freopen("in.txt", "r", stdin); solve(); }