随笔-141  评论-9  文章-3  trackbacks-0
 
pku 3628 Bookshelf 2 (01背包)

题目意思是给你n个数，其中选取一些数使他们的和sum大于给定数M，求满足此条件的Min{M-sum},此题可以装化为01背包问题，刚开始可以把所有的数都加起来这时的sum一定大于M的，但此时的sum-M不一定是最小的，怎么才能得到最小的呢。可以这样想，令B=sum-M，要尽量在这B中减去一些原来加进去数，这样会使sum-M的差逐渐减小，这不就是01背包的模型吗，背包的容量为B，物品的价值与体积相同。尽量使其价值最大，那最后的到的差当然就是最小的。

#include <iostream>

using namespace std;

int N,H;

int cows[25];
int f[1000001];

int inline max(int a, int b){
    return a>b?a:b;
}

int main(){
    int sum=0, i,j;
    cin>>N>>H;

    for(i=1; i<=N; ++i){
        cin>>cows[i];
        sum+=cows[i];
    }

    int m = sum - H;

    for(i=1; i<=N; ++i)
        //ZeroOnePack(w[i], c[i])
        for(j=m; j>=cows[i]; --j)
            f[j]=max(f[j], f[j-cows[i]]+cows[i]);


    cout<<m-f[m]<<endl;
    return 0;
}


参考:http://hi.baidu.com/zhouxc07/blog/item/898a103c35b886ce9e3d6262.html
posted @ 2010-12-08 11:21 小阮 阅读(247) | 评论 (0) | 编辑 收藏
USACO 2.4.1 The Tamworth Two
/*
ID: lorelei3
TASK: ttwo
LANG: C++
*/

#include <fstream>

using namespace std;

ifstream fin;
ofstream fout;

const int MAX = 10000000;

int dx[] = { -1, 0, 1,  0 };
int dy[] = {  0, 1, 0, -1 };

int cd=0, cx, cy;
int fd=0, fx, fy;

int map[10][10];

int main(){
    int i,j;
    char ch;

    fin.open("ttwo.in");
    fout.open("ttwo.out");

    for(i=0; i<10; i++)
        for(j=0; j<10; j++){
            fin>>ch;
            if(ch=='*'){
                map[i][j]=1;
            }else if(ch=='C'){
                cx=i, cy=j;
            }else if(ch=='F'){
                fx=i, fy=j;
            }
        }
        
    int step=0;
    int x,y;
    while(step!=MAX){

        // for cows
        x = cx+dx[cd];
        y = cy+dy[cd];
        if(map[x][y]==1 || x<0 || x>9 || y<0 || y>9)
            cd = (cd+1)%4;
        else{
            cx = x;
            cy = y;
        }

        // for farmer
        x = fx+dx[fd];
        y = fy+dy[fd];
        if(map[x][y]==1 || x<0 || x>9 || y<0 || y>9)
            fd = (fd+1)%4;
        else{
            fx = x;
            fy = y;
        }

        step++;

        //compare
        if(cx==fx && cy==fy)
            break;
    }

    if(step == MAX)
        fout<<0<<endl;
    else
        fout<<step<<endl;
    return 0;
}


posted @ 2010-12-08 11:18 小阮 阅读(212) | 评论 (0) | 编辑 收藏
USACO 2.3.5 Controlling Companies
唉..做得烂洗了..

/*
ID: lorelei3
TASK: concom
LANG: C++
*/

#include <fstream>
#include <memory.h>

using namespace std;

const int MAX = 101;
const int NCON = 100;
int N,x;
int a[MAX][MAX];
int c[MAX];
bool f[MAX];
ifstream fin;
ofstream fout;

void dfs(int k){
    f[k]=true;
    for(int i=1; i<=NCON; ++i){
        c[i] += a[k][i];
        if(!f[i] && c[i]>50){
            dfs(i);
        }
    }
}

void show(){
    for(int i=1; i<=NCON; ++i)
            if(i!=x && c[i]>50)
                fout<<x<<" "<<i<<endl;
    return;
}

int main(){
    int i,j,p,k;

    fin.open("concom.in");
    fout.open("concom.out");

    fin>>N;

    for(k=0; k<N; k++){
        fin>>i>>j>>p;
        a[i][j]=p;
    }

    for(k=1; k<=NCON; ++k){
        memset(f, 0, sizeof(f));
        memset(c, 0, sizeof(c));
        x=k;
        dfs(k);
        show();
    }
    return 0;
}
posted @ 2010-12-07 21:28 小阮 阅读(477) | 评论 (0) | 编辑 收藏
pku 2624 Charm Bracelet (01背包)
很标准的01 背包问题

for(i=1; i<=N; ++i)
//ZeroOnePack( w[i], c[i])
   for(j = V; j>= weight; j--)
      f[j] = max( f[j], f[j-cost[i]]+w[i])

#include <iostream>

using namespace std;

int w[3500], d[3500];
int f[13000];
int N,M;

inline int max(int a, int b){
    return a>b? a: b;
}

int main(){
    int i,j;
    cin>>N>>M;

    for(i=1; i<=N; ++i)
        cin>>w[i]>>d[i];

    for(i=1; i<=N; ++i)
        // ZeroOnePack(w[i], d[i])
        for(j=M; j>=w[i]; j--)
            f[j] = max(f[j], f[j-w[i]]+d[i]);
    
    cout<<f[M]<<endl;

    return 0;
}

posted @ 2010-12-07 16:05 小阮 阅读(151) | 评论 (0) | 编辑 收藏
pku 1837 Balance (01背包)
01 背包问题.

f[i][j] 表示将前i个物品放入力矩为j的可行方案

f[i][j] = sum{ f[i-1][j-w[i][k] }

#include <iostream>

using namespace std;

const int mid = 6000;

int w[25],v[25];
int f[25][mid+mid];

int C,G;

int main(){
    int i,j,k;

    cin>>C>>G;

    for(i=1; i<=C; ++i) cin>>v[i];
    for(i=1; i<=G; ++i) cin>>w[i];

    for(i=1; i<=C; ++i)
        f[1][mid+v[i]*w[1]] = 1;

    for(i=2; i<=G; ++i)
        for(j=1; j<=C; ++j)
            for(k=0; k<=2*mid; ++k)
                if(f[i-1][k]>0)
                    f[i][k+w[i]*v[j]] += f[i-1][k];

    cout<<f[G][mid]<<endl;

    return 0;
}

posted @ 2010-12-07 12:18 小阮 阅读(109) | 评论 (0) | 编辑 收藏
USACO 2.3.4 Money Systems
完全背包问题.

只是将完全背包问题的max 改为 sum

/*
ID: lorelei3
TASK: money
LANG: C++
*/

#include <fstream>

using namespace std;

const int V = 30;
const int MAX = 10005;

long long  f[MAX];
int c[V];
int N;

int main(){
    int i,j,n;
    ifstream fin;
    ofstream fout;

    fin.open("money.in");
    fout.open("money.out");

    fin>>n>>N;
    for(i=1; i<=n; ++i)
        fin>>c[i];

    f[0]=1;
    for(i=1; i<=n; ++i)
        for(j=c[i]; j<=N; ++j)
            f[j] = f[j] + f[j-c[i]];

    fout<<f[N]<<endl;
    return 0;
}
posted @ 2010-12-06 13:14 小阮 阅读(112) | 评论 (0) | 编辑 收藏
USACO 2.2.4 Party Lamps

/*
ID: lorelei3
TASK: lamps
LANG: C++
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


const int C = 4;
const int MAXN = 6;
const int MASK = (1<<MAXN)-1;
int loc[1<<MAXN];

int n,c,t;
int open_mask, tot_mask;
int op[4] = {    MASK, 
                MASK & 0xAA, 
                MASK & 0x55,
                MASK & ( (1<<(MAXN-1)) | (1<<(MAXN-4)) )
};

FILE *fin, *fout;

void wirte(int lights){
    int i;
    char s[105];
    for(i=0; i<n; ++i)
        s[i] = ( lights & (1<<(MAXN-1-(i%MAXN))) ) ? '1': '0';
    s[i]='\0';
    fprintf(fout, "%s\n", s);
}

void dfs(int lights, int i, int n){
    if(n==c){
        if( (lights&tot_mask)==open_mask){
            loc[lights]=1;
            return;
        }
    }else
        for( ; i<4; ++i)
            dfs( lights^op[i], i+1, n+1);
}

int main(){
    int i;

    fin  = fopen("lamps.in", "r");
    fout = fopen("lamps.out", "w");
    
    assert(fin!=NULL && fout!=NULL);

    fscanf(fin, "%d %d", &n, &c);

    for(;;){
        fscanf(fin, "%d", &t);
        if(t==-1) break;
        t = MAXN-1-(t-1)%MAXN;
        open_mask |= (1<<t);
        tot_mask |= (1<<t);
    }

    for(;;){
        fscanf(fin, "%d", &t);
        if(t==-1) break;
        t = MAXN-1-(t-1)%MAXN;
        tot_mask |= (1<<t);
    }

    if(c>4){
        if(c%2==0)
            c=4;
        else
            c=3;
    }

    for(i=0; i<=c; i+=2)
        dfs(MASK, 0, i);

    bool flag=false;
    for(i=0; i< (1<<MAXN); ++i)
        if(loc[i]){
            flag = true;
            wirte(i);
        }

    if(!flag)
        fprintf(fout, "IMPOSSIBLE\n");

    return 0;
}
posted @ 2010-11-21 00:49 小阮 阅读(136) | 评论 (0) | 编辑 收藏
USACO 2.2.3 Runaround Numbers


/*
ID: lorelei3
TASK: runround
LANG: C++
*/
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;

const int N = 15;

bool num_check(int n){
    char num[N];
    bool used[10];
    int i, len;

    memset(used, 0, sizeof(used));

    sprintf(num, "%d", n);

    len=strlen(num);

    for(i=0; i<len; ++i)
        if(used[num[i]-'0'] == true || num[i]=='0')
            return false;
        else
            used[num[i]-'0'] = true;
    return true;
}

bool round_check(int n){
    char num[N];
    bool f[N];
    int steps, i, len;

    memset(f, 0, sizeof(f));

    sprintf(num, "%d", n);

    len=strlen(num);

    steps=0, i=0;

    while(steps<len){
        if(f[i]==true)
            return false;
        else
            f[i] = true;
        i = (i+num[i]-'0') % len;
        steps++;
    }
    if(i==0)
        return true;
    else
        return false;
}

int main(){

    int n,num;

    ifstream in("runround.in");
    ofstream out("runround.out");

    in>>n;

    for(num=n+1; ;num++)
        if(num_check(num) && round_check(num))
            break;
    
    out<<num<<endl;
        
    return 0;
}
posted @ 2010-11-21 00:49 小阮 阅读(174) | 评论 (0) | 编辑 收藏
USACO 2.2.2 Subset Sums

/*
ID: lorelei3
TASK: subset
LANG: C++
*/

#include<stdio.h>

const int N = 40;
const int MAX = (1+N)*N/4;

long long ans[N][MAX];

int main(){

    int n, tot, sum;

    freopen("subset.in", "r", stdin);    
    freopen("subset.out", "w", stdout);       
    
    scanf("%d", &n); 

    tot = (1+n)*n/2;

    if(tot&0x01){
        printf("0\n");
        return 0;
    }

    sum = tot/2;

    ans[1][0] = 1; ans[1][1] = 1;

    for(int i=2; i<=n; ++i)
        for(int j=0; j<=sum; ++j)
            if(j-i>=0)
                ans[i][j]=ans[i-1][j]+ans[i-1][j-i];
            else
                ans[i][j]=ans[i-1][j];

    printf("%lld\n", ans[n][sum]/2);

    return 0;
}
posted @ 2010-11-21 00:48 小阮 阅读(168) | 评论 (0) | 编辑 收藏
USACO 2.2.1 Preface Numbering

/*
ID: lorelei3
TASK: preface
LANG: C
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
 
static char *encode[] = {
    "", "I", "II", "III", "IV",
    "V", "VI", "VII", "VIII", "IX",
};
 
char*
romandigit(int d, char *ivx)
{
    char *s, *p;
    static char str[10];
 
    for(s=encode[d%10], p=str; *s; s++, p++) {
        switch(*s){
        case 'I':
            *p = ivx[0];
            break;
        case 'V':
            *p = ivx[1];
            break;
        case 'X':
            *p = ivx[2];
            break;
        }
    }
    *p = '\0';
    return str;
}
 
char*
roman(int n)
{
    static char buf[20];
 
    strcpy(buf, "");
    strcat(buf, romandigit(n/1000, "M"));
    strcat(buf, romandigit(n/100,  "CDM"));
    strcat(buf, romandigit(n/10,   "XLC"));
    strcat(buf, romandigit(n,      "IVX"));
    return buf;
}
 
int 
main(void)
{
    FILE *fin, *fout;
    int i, n;
    char *s;
    int count[256];
 
    fin = fopen("preface.in", "r");
    fout = fopen("preface.out", "w");
    assert(fin != NULL && fout != NULL);
 
    fscanf(fin, "%d", &n);
 
    for(s="IVXLCDM"; *s; s++)
        count[*s] = 0;
 
    for(i=1; i<=n; i++)
        for(s=roman(i); *s; s++)
            count[*s]++;
 
    for(s="IVXLCDM"; *s; s++)
        if(count[*s])
            fprintf(fout, "%c %d\n", *s, count[*s]);
 
    return 0;
}
posted @ 2010-11-21 00:47 小阮 阅读(145) | 评论 (0) | 编辑 收藏
仅列出标题
共14页: First 6 7 8 9 10 11 12 13 14 
Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮