Codeforces Round #198 (Div. 1) B,C 动态规划

　　比赛时，开了大号去做，算了半天发现不会做A，囧。于是跑去看B，发现很水？于是很快敲完了，但是A不会，没敢交。于是去看C，一直找规律啊，后来总算调了出来，看了一下榜，发现还是算了吧，直接去睡觉了。第二天一起床把代码一交，居然A了,发现交的话rating还能涨一点，囧。

B：其实就是求一个最长不下降子序列的长度。注意到数据范围，使用二分的方式求解。

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define debug puts("here")

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

#define REP(i,a,b) for(int i=a;i<=b;i++)

#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)

#define pb push_back

#define RD(n) scanf("%d",&n)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)

#define All(vec) vec.begin(),vec.end()

#define MP make_pair

#define PII pair<int,int>

#define PQ priority_queue

#define cmax(x,y) x = max(x,y)

#define cmin(x,y) x = min(x,y)

#define Clear(x) memset(x,0,sizeof(x))

/*

#pragma comment(linker, "/STACK:1024000000,1024000000")

int size = 256 << 20; // 256MB

char *p = (char*)malloc(size) + size;

__asm__("movl %0, %%esp\n" :: "r"(p) );

*/

/******** program ********************/

const int MAXN = 100005;

int a[MAXN];

int dp[MAXN];

int q[MAXN];

int n;

void cc(){

    int top = 0;

    rep1(i,n){

        if(top==0||dp[top]<a[i]){

            dp[++top] = a[i];

            continue;

        }

        int l = 1 , r = top;

        int ans = 1;

        while(l<=r){

            int mid = (l+r)>>1;

            if(dp[mid]<a[i])

                l = mid+1;

            else{

                ans = mid;

                r = mid-1;

            }

        }

        dp[ans] = a[i];

    }

    cout<<top<<endl;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("sum.in","r",stdin);

    //freopen("sum.out","w",stdout);

#endif

    while(cin>>n){

        rep1(i,n)

            RD(a[i]);

        cc();

    }

    return 0;

}

C：注意变与不变的部分。

假设现在有位置：1,2,3,4,5,6

需要填入的数为：1,2,3,4,7,8

则可以分成两个部分：右边的可以匹配任意位置。

位置：1,2,3,4　　5,6

数： 1,2,3,4　　7,8

1.当左边的数1匹配上左边时，不妨假设1-2，则左边消除了两个，右边增加一个：数2可以匹配其他的所有位置

2.当左边的数1匹配上右边时，不妨假设1-5，则左边消除了一个，右边数目不变（消除了5，添加了1）

3.当右边的数7匹配上左边时，不妨假设7-1，则左边消除了一个，右边数目不变（消除了7，添加了1）

4.当右边的数7匹配上右边时，不妨假设7-5，则左边不变，右边数目减少一个

所以可以dp，dp[i][j]表示左边有i个，右边有j个时的方案数。

1.当i=0时，为p[j]（p[j]表示j的排列）

2.当i=1时，左边任意匹配右边一位，右边数目不变，因此方案数为为p[j]*j。

#include <set>

#include <map>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define debug puts("here")

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

#define REP(i,a,b) for(int i=a;i<=b;i++)

#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)

#define pb push_back

#define RD(n) scanf("%d",&n)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)

#define All(vec) vec.begin(),vec.end()

#define MP make_pair

#define PII pair<int,int>

#define PQ priority_queue

#define cmax(x,y) x = max(x,y)

#define cmin(x,y) x = min(x,y)

#define Clear(x) memset(x,0,sizeof(x))

/*

#pragma comment(linker, "/STACK:1024000000,1024000000")

int size = 256 << 20; // 256MB

char *p = (char*)malloc(size) + size;

__asm__("movl %0, %%esp\n" :: "r"(p) );

*/

/******** program ********************/

const int MAXN = 2005;

const int MOD = 1e9+7;

ll dp[MAXN][MAXN];

int a[MAXN],n;

bool use[MAXN];

ll p[MAXN];

ll dfs(int x,int y,int res){

    if(res<=0) return p[y];

    if(x==1)return p[y]*y%MOD;

    if(x==0)return p[y];

    if(~dp[x][y])return dp[x][y];

    ll tmp = (x-1);

    tmp *= dfs(x-2,y+1,res-2);

    tmp += dfs(x-1,y,res-1)*y;

    return dp[x][y] = tmp%MOD;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("sum.in","r",stdin);

    //freopen("sum.out","w",stdout);

#endif

    p[0] = p[1] = 1;

    for(int i=2;i<MAXN;i++)

        p[i] = p[i-1]*i%MOD;

    while(cin>>n){

        Clear(use);

        rep1(i,n){

            RD(a[i]);

            if(~a[i])

                use[ a[i] ] = true;

        }

        int x = 0 , y = 0;

        rep1(i,n){

            if(a[i]==-1){

                if(use[i])y ++;

                else    x ++;

            }

        }

        memset(dp,-1,sizeof(dp));

        cout<<dfs(x,y,x+y)<<endl;

    }

    return 0;

}

巴特西

Codeforces Round #198 (Div. 1) B,C 动态规划

最新文章

热门文章