算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
吐槽:
    1. 最近因为一些考试/数据结构试验报告,等琐事连续N天没有做题,也就没有更新blog了。真是罪过罪过…………
    2. 600pt 代码偏长(T_T) 最后时刻没有调出来,等考完试奉献上代码。
    3. 和HIT的学长分到一个房间了Orz....
250pt
有两个集合,每个集合有N(N<50)个锥面(表示为高H和底面半径R,均小于10,000)。要求从集合1和集合2的笛卡尔积集合中选取最多的元素满足如下性质:
    1. Ha / Ra > Hb / Rb
    2. Ra < Rb
算法分析:
    裸二分匹配,貌似贪心也可
#include<iostream>
#include<vector>
using namespace std;
int G[55][55];
int n,m,yM[55],chk[55];
int dfs(int u){
    for(int v=0; v<m;v++) if(G[u][v] && !chk[v]){
        chk[v] = 1;
        if(yM[v]==-1 || dfs(yM[v])){
            yM[v] = u; return 1;
        }
    }
    return 0;
}
bool judge(int th,int tr, int bh, int br){
    return br > tr && br*th >tr*bh;
}
class PointyWizardHats{
    public : int getNumHats(vector <int> th, vector <int> tr, vector <int> bh, vector <int> br){
        n = th.size(), m = bh.size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(judge(th[i],tr[i],bh[j],br[j]))
                    G[i][j] =1;
        int ans=0;
        for(int i=0;i<m;i++) yM[i] = -1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++) chk[j] = 0;
            ans += dfs(i);
        }
        return ans;
    }
};
600pt
A和B博弈。 在N*N(N<=13)的矩阵上,有一些 ’H‘ 格子, 一开始每个H格子里最多有一枚带权值的硬币。 每次小B选一个H格子,然后小A将硬币任意排列后,将该格子的硬币给小B。
排列后必须满足如下条件:
    1. 每个格子必须有最多一枚硬币,小B选的格子可以没有硬币
    2. 每一行,H的个数和硬币的个数之和必须是偶数
    3. 每一列也一样。
小B想让硬币的权值和最多,小A反之。
小B选择一个格子后,那个格子上就不能在转移硬币了。如果有就永远有,没有就永远没有。
问两人都用最优策略,B得到的分数和是多少。
算法分析:
    博弈DP: dp[mask] mask是三进制,1表示已经选择了那个格子,2表示那个格子上有硬币。
    之前要预处理一遍,检查某个状态是否是合法的。
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 13;
pair<int,int> pos[N];
bool can[1600000],row[N],col[N];
int count(int mask){
    int a = 0;
    while(mask) a += mask & 1, mask >>= 1;
    return a;
}
int dp[1600000],base[20],cont[1<<N],n,cns;
int cal(int a,int b){
    int ans=0;
    for(int i=0;i<n;i++){
        ans += base[i] * ((a&1) + (b&1));
        a>>=1, b>>=1;
    }
    return ans;
}
const int inf = 100;
void OP(int msk){for(int i=0;i<n;i++,msk>>=1)cout<<(msk&1);cout<<" ";}
int dfs(int msk1,int msk2,int m){
    
    if(m==0) return 0;
    int &ans = dp[cal(msk1,msk2)];
    if(ans!=-1) return ans;
    for(int i=0;i<n;i++)if((1<<i) & msk1);else{
        int nmask = msk1 ^ (1<<i),l=inf,r=inf;
        if(can[cal(nmask,msk2)]) l = dfs(nmask,msk2,m-1);
        if(can[cal(nmask,msk2 ^ (1<<i))]) r = dfs(nmask,msk2 ^ (1<<i),m-1)+1;
        if(l > r) l = r;
        if(l>=inf) continue;
        if(ans < l) ans = l;
    }
    return ans;
}
class MagicalHats{
    public : 
    int findMaximumReward(vector <string> G, vector <int> coins, int m){
        n = 0;
        int flag,k, ans = 0;cns = coins.size();
        memset(dp,-1,sizeof(dp));
    //    memset(hash,-1,sizeof(hash));
        for(int i=0;i<G.size();i++)
            for(int j=0;j<G[0].size();j++)
                if(G[i][j] == 'H'){
                    pos[n++] = make_pair(i,j);
                }
        base[0] = 1;
        for(int i=1;i<n;i++) base[i] = 3*base[i-1];
        int l1=G.size(),l2=G[0].size();
        for(int i=0;i<(1<<n);i++) cont[i] = count(i);
        for(int msk1 = 0; msk1 < (1<<n); msk1 ++){
            for(int msk2 = 0; msk2 < (1<<n); msk2 ++){
                if(cont[msk2] != cns) continue;
                if(can[k=cal(msk1,msk2 & msk1)]) continue;
                for(int i=0;i<l1;i++) row[i] = 0;
                for(int i=0;i<l2;i++) col[i] =0;
                for(int i=0;i<n;i++) if((1<<i) & msk2);else row[pos[i].first]^=1, col[pos[i].second] ^=1;
                flag = 0;
                for(int i=0;i<G.size();i++) flag |= row[i];
                for(int i=0;i<G[0].size();i++) flag |= col[i];
                if(flag) continue;
                can[k] = 1;
            }
            if(msk1 && !can[0]) return -1;
        }
    //    cout<<"."<<endl;
        if(!can[0]) return -1;
        k = dfs(0,0,m);
        sort(coins.begin(), coins.end());
        for(int i=0;i < k; i++) ans += coins[i];
        return ans;
    }
};
posted on 2012-07-09 21:49 西月弦 阅读(432) 评论(0)  编辑 收藏 引用 所属分类: 比赛感言

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