算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
这场只出了一道题,掉了很多分。D题和E题近期补上。

A

题目描述:
   有N(N<200)项工作。每项工作必须在一个模式下花费1个单位时间完成,工作之间的完成顺序存在依赖关系,形成DAG图。一共有三种模式(0,1,2)。模式之间的切换时间为
[0,1,2]
[2,0,1]
[1,2,0]
一开始你可以0花费选择一种模式,问完成所有工作的最少时间。

算法分析:
   拓扑排序+贪心法。
   假设我目前在模式A,那么第一步一定要一口气把A模式的任务全都完成。
   然后要选择模式切换代价较小的模式。因为这样的模式最多只有一种,所以就可以轻松解决了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int flag[3][3] = {
    {0,1,2},{2,0,1},{1,2,0}
};
const int N = 205;
int num[N] , G[N][N], Du[N], tmp[N],vis[N],n;
int work(int p){
//    cout<<"p: "<<p<<endl;
    int v = 0,f = 0;
    while(1){
        f = 0;
        for(int i=0;i<n;i++) if(!Du[i] && !vis[i] && num[i] == p){
//            cout<<i<<" ";
            vis[i] = 1;
            v++;
            for(int v=0;v<n;v++) if(!vis[v] && G[i][v]) 
                Du[v]--;
            f = 1;
        }
        if(!f) break;
    }
//    cout<<endl;
    for(int i=0;i<n;i++) if(!Du[i] && !vis[i] && flag[p][num[i]] == 1){
        v += 1 + work(num[i]);
        return v;
    }
    for(int i=0;i<n;i++) if(!Du[i] && !vis[i]) {
        v += 2 + work(num[i]);
        return v;
    }
    return v;
}
int main(){
    while( cin >> n){
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                G[i][j] = 0;
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
            num[i]--;
        }
        int t;
        memset(tmp,0,sizeof(tmp));
        for(int i=0;i<n;i++){
            cin >> tmp[i];
            for(int oo=0;oo<tmp[i];oo++){
                int u;
                cin >> u;
                u --;
                G[u][i] = 1;
            }
        }
        int ans = ~0u>>2;
        for(int p=0;p<3;p++)
            for(int i=0;i<n;i++)
                if(!tmp[i] && p == num[i]){
                    memset(vis,0,sizeof(vis));
                    for(int i=0;i<n;i++) Du[i] = tmp[i];
                    int v =work(p);
//                    cout<<"ans: "<<p<<" "<<v<<endl;
                    if(v<ans) ans = v;
                    break;
                }
        cout<< ans << endl;
    }
}

B

给出一个序列a[10](a[i]<100),和N(N<100)。构造一个长度为N的数字,要求
   1.没有前导0
   2.数字i不少于a[i]个
求构造方法数。

算法分析:
   典型的动态规划求解。
   dp[i][j]表示前j个数字构成符合条件的长度为i的数字的方法数。
   显然dp[i][j] = sum(dp[k][j-1] * C[i][k]) 其中k>0 && k<=i-a[j]
   组合数预处理出来即可,其中要考虑转移0的问题,这个留给大家思考吧~~

#include<iostream>
#include<cstdio>
using namespace std;
const int mod = (int)1e9 + 7;
typedef long long ll;
const int N = 105;
ll C[N][N];
void OP(int msk){
    for(int i=0;i<10;i++, msk>>=1)
        cout<<(msk&1);cout<<" ";
}
int main(){
    for(int i=0;i<N;i++) {
        C[i][0] = 1;
        for(int j=1;j<=i;j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
    }
    int n, a[11];
    static ll dp[N][1<<11];
    while(cin >> n){
        for(int i=0;i<10;i++){
            cin >> a[i];
        }
        dp[0][0] =1;
        for(int i = 0; i<=n; i++){
            for(int msk = 1; msk < (1<<10); msk++){
                ll &t = dp[i][msk] ;
                t = 0;
                for(int p = 0; p < 10; p++) if((1<<p) & msk){
                    ll s = 0;
                    for(int j=0;j<=i-a[p];j++){
                        if(p) s += C[i][i-j] * dp[j][msk^(1<<p)];
                        else s += i ?C[i-1][i-j]*dp[j][msk^(1<<p)] : 0;
                        s %= mod;
                        if(s){
//                            cout<<i<<" ";OP(msk);cout<<j<<" "<<p<<" "<<dp[j][msk^(1<<p)]<<endl;
//                            cout<<s<<endl;
                        }
                    }
                    t = (t+s) % mod;
                    break;
                }
            }
        }
        ll ans = 0;
        for(int i = 1; i<=n; i++)
            ans = (ans + dp[i][(1<<10)-1]) % mod;
        cout<< ans << endl;
    }
}

C

给一个N*N的矩阵(N<300),权值范围是[-1000,1000]。现在让你从右上角走到左下角,只能向下或者向右走,走两次,每个格子最多取一次权值,问最大能取到的值是多少。

算法分析:

因为格子上的权值可能是负数,所以费用流ggg。
考虑动态规划,想像两次是两个人a,b同时走的,在走了i步之后,a的x值是xa,b的x值是xb。
dp[i][xa][xb]记为此时可以获取的最大权值。
转移就很简单了,呵呵~

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 305;
int dp[2][N][N], num[N][N],n;
const int inf = ~0u>>2;
inline bool chk(int x,int y){
    return x >=0 && y >=0 && x <n && y <n;
}
inline void chkmax(int &a,const int b){if(a<b)a=b;}
int main(){
    while(cin >> n){
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin >> num[i][j] ;
        int ans = (dp[0][0][0] = num[0][0]);
        for(int i=1;i<2*n-1;i++) 
            for(int p = (i>=n)? i-n+1: 0; p < min(n,i+1); p++) {
                for(int q = p; q< min(n,i+1); q++) {
                    int v;
                    if(q == p) v = num[p][i-p];
                    else v = num[p][i-p] + num[q][i-q];
                    dp[i&1][p][q] = -inf;
                    for(int oo = 0; oo<2;oo++){
                        int nx1 = p - (oo==0);
                        int ny1 = i-p - (oo==1);
    //                    cout<<nx1<<" "<<ny1<<endl;
                        if(!chk(nx1,ny1)) continue;
                        for(int uu = 0; uu<2; uu++){
                            int nx2 = q - (uu==0);
                            int ny2 = i-q - (uu==1);
    //                        cout<<nx2<<" "<<ny2<<endl;
                            if(!chk(nx2,ny2)) continue;
                            int x1 = nx1,x2 =nx2;
                            if(x1>x2) swap(x1,x2);
    //                        if(p==q)    cout<<p<<" "<<i-p<<" "<<nx1<<" "<<nx2<<endl;
                            chkmax(dp[i&1][p][q], dp[i-1&1][x1][x2] + v);
                        }
                    }
                    ans = dp[i&1][p][q];
//                    if(p==q)    cout<<"i: "<<i<<" "<<p<<" "<<q<<" "<<ans<<endl;
                }
            }
        cout << ans << endl;
    }
    return 0;    
}




posted on 2012-08-03 15:36 西月弦 阅读(269) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理