2013-C15-team5

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
小结by AIdancer：
   Kotomi，gdb可以不用，但是不可以不会，抽空补一下。
   看似常数没优化好，其实是自己基础不扎实，模板也不会用。。。先把模板补好吧，多说无益，抓紧干。
}}}

{{{
小结 by Kotomi
   那题矩阵乘法写错一个位置没看出来浪费了比较多时间...
   习惯了用输出调试并且不怎么用IDE，这个习惯比较难改= =b
}}}

{{{
Derangement-hdu4689

Solution:
时间复杂度O(n^2)的dp(n为字符串长度)
f[i][j]表示前i个字符里面只有j个'+'没有填上数字的方案数.
转移方程: 
f[i][j] = f[i-1][j]*j + f[i-1][j+1]*(j+1)*(j+1);    (str[i]=='-')
f[i][j] = f[i-1][j-1] + f[i-1][j]*j;                (str[i]=='+')

若str[i] = '-',那么第i个位置一定要被填掉,并且只能从前面i-1个数里面选择.
(1)如果当前不使用第i个数字,那么前i-1个数字里有j个数字没有使用过,所以有j种方法从f[i-1][j]得到当前状态.
(2)如果当前使用第i个数字,那么前面有j+1个坑(即未被匹配的'+')可以跳,并且前i-1个数字里有j+1个数字未被使用,所以有(j+1)^2种方法从f[i-1][j+1]得到当前状态.

若str[i] = '+',该位置不需要由前面的数字来填,所以f[i][j] = f[i-1][j-1] + f[i-1][j]*j;

Code:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long f[21][21],n;
char str[21];

int main(){
    while (scanf("%s",str)!=EOF){
        n=strlen(str);
        if (n==1 || str[0]=='-' || str[n-1]=='+'){ puts("0"); continue; }
        memset(f,0,sizeof(f));
        f[0][1]=1;
        int i,j;
        for (i=1; i<n; i++){
            if (str[i]=='-')
                for (j=0; j<n; j++) f[i][j]=f[i-1][j]*j+f[i-1][j+1]*(j+1)*(j+1);
            if (str[i]=='+')
                for (j=1; j<n; j++) f[i][j]=f[i-1][j-1]+f[i-1][j]*j;
        }
        cout << f[n-1][0] << endl;
    }
    return 0;
}
}}}
小结by AIdancer：
   Kotomi，gdb可以不用，但是不可以不会，抽空补一下。
   看似常数没优化好，其实是自己基础不扎实，模板也不会用。。。先把模板补好吧，多说无益，抓紧干。

小结 by Kotomi
   那题矩阵乘法写错一个位置没看出来浪费了比较多时间...
   习惯了用输出调试并且不怎么用IDE，这个习惯比较难改= =b

Derangement-hdu4689
Solution:
时间复杂度O(n^2)的dp(n为字符串长度)
f[i][j]表示前i个字符里面只有j个'+'没有填上数字的方案数.
转移方程: 
f[i][j] = f[i-1][j]*j + f[i-1][j+1]*(j+1)*(j+1);    (str[i]=='-')
f[i][j] = f[i-1][j-1] + f[i-1][j]*j;                (str[i]=='+')
若str[i] = '-',那么第i个位置一定要被填掉,并且只能从前面i-1个数里面选择.
(1)如果当前不使用第i个数字,那么前i-1个数字里有j个数字没有使用过,所以有j种方法从f[i-1][j]得到当前状态.
(2)如果当前使用第i个数字,那么前面有j+1个坑(即未被匹配的'+')可以跳,并且前i-1个数字里有j+1个数字未被使用,所以有(j+1)^2种方法从f[i-1][j+1]得到当前状态.
若str[i] = '+',该位置不需要由前面的数字来填,所以f[i][j] = f[i-1][j-1] + f[i-1][j]*j;
Code:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long f[21][21],n;
char str[21];
int main(){
    while (scanf("%s",str)!=EOF){
        n=strlen(str);
        if (n==1 || str[0]=='-' || str[n-1]=='+'){ puts("0"); continue; }
        memset(f,0,sizeof(f));
        f[0][1]=1;
        int i,j;
        for (i=1; i<n; i++){
            if (str[i]=='-')
                for (j=0; j<n; j++) f[i][j]=f[i-1][j]*j+f[i-1][j+1]*(j+1)*(j+1);
            if (str[i]=='+')
                for (j=1; j<n; j++) f[i][j]=f[i-1][j-1]+f[i-1][j]*j;
        }
        cout << f[n-1][0] << endl;
    }
    return 0;
}
附加文件