con open 详细 序列 ons src efi com html
题目链接:hdu 4055 Number String
题意:
给你一个长度为n的指定的升降序列,问有多少种排列,符合这样的序列。
题解:
训练赛的时候没想出来,大概这种排列的dp需要转换一下思维吧。
考虑dp[i][j]表示前i个数只用1~i,结尾为j。
然后就有
如果s[i - 1]是‘ I ‘,那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + .. + dp[i-1][1]。
如果s[i - 1]是‘D’,那么dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i]。
如果s[i - 1]是‘?’,那么dp[i][j] = dp[i-1][i-1] + ... + dp[i-1][1]。
比较巧妙。需要好好想想,详细题解:传送门
- #include < bits / stdc++.h > #define F(i, a, b) for (int i = (a); i <= (b); ++i) using namespace std;#define mst(a, b) memset(a, b, sizeof(a))
- const int N = 1007,
- P = 1e9 + 7;
- char s[N];
- int dp[2][N],
- n,
- x;
- void up(int & a, int b) {
- a += b;
- if (a >= P) a -= P;
- }
- int main() {
- while (~scanf("%s", s + 1)) {
- n = strlen(s + 1) + 1;
- mst(dp, 0),
- dp[x = 0][1] = 1;
- F(i, 2, n) {
- x ^= 1,
- mst(dp[x], 0);
- if (s[i - 1] == ‘ ? ‘) {
- F(j, 1, i - 1) up(dp[x][1], dp[x ^ 1][j]);
- F(j, 2, i) up(dp[x][j], dp[x][1]);
- } else if (s[i - 1] == ‘I‘) {
- F(j, 1, i) up(dp[x][j], dp[x][j - 1] + dp[x ^ 1][j - 1]);
- } else {
- for (int j = i; j; j--) up(dp[x][j], dp[x][j + 1] + dp[x ^ 1][j]);
- }
- }
- int ans = 0;
- F(i, 1, n) up(ans, dp[x][i]);
- printf("%d\n", ans);
- }
- return 0;
- }
hdu 4055 Number String(排列dp)
来源: http://www.bubuko.com/infodetail-2334919.html