摘要: 下面我先說以下拓撲排序：
嚴蔚敏《數據結構》上的定義是：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
拓撲排序的具體做法是：
1.在有向圖中選擇一個沒有前驅（入度為0）的頂點，輸出
2.從圖中刪除該頂點和所有以它為尾的弧，并更新相關點的入度
3.重復1，2步，直到所有頂點都被輸出，或者發現圖中存在回路。  閱讀全文 題意描述：
有幾種面額固定的硬幣，每種面額的硬幣都有無數張。給你一定的金額，問總共有多少種找零方案。
完全背包問題，動態方程為：f[j] += f[j - mny[i]];
myi[i]表示第i種硬幣的面值，f[j]表示數額為j的找零方案。
表示對完全背包的動態方程不甚理解，希望大神不惜指點。。
以下是本題代碼：
題意描述：
給定一定數量的不同面值的鈔票，輸出由這些鈔票組成的不超過出款上限（題目中的cash）的最大金額。
01背包問題，請參閱：http://m.shnenglu.com/hoolee/archive/2012/08/14/187179.html

     摘要: 01背包的狀態轉移方程為：
當v當v>=Ci時f[i,v]=Max(f[i-1,v],f[i-1,v-Ci]+Wi);(2)//當第i件物品能夠放下時，我們可以選擇放，或不放，取決于總價值的大小。
其中v為當前背包的中容量，Ci表示第i件物品的體積，Wi表示第i件物品的價值，f[i,v]表示容量為v的背包在考慮前i件物品后的最大價值。  閱讀全文

posted @ 2012-08-14 16:32 小鼠標 閱讀(1558) | 評論 (0) | 編輯 收藏

poj2063--01背包

題意描述：有幾種不同的債券共購買，每種債券有相應的年效益，這些債券每年可以兌現一次，并且沒有任何手續費，兌現后可以選擇購買不同債券。給定初始金額和年限，求出最終的最大收益。
解題思路：每年按01背包問題計算一遍即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100000
typedef struct
{
    int w;
    int i;
}Bonds;
int f[LEN];
Bonds bd[20];
int Max(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
int main()
{
    int i, j, k;
    int N;
    int M, Y;
    int d, a, b;
    scanf("%d", &N);
    while(N--)
    {
        scanf("%d%d", &M, &Y);
        scanf("%d", &d);
        for(i = 1; i <= d; i++)
        {
            scanf("%d%d", &bd[i].w, &bd[i].i);
            bd[i].w /= 1000;//債券的面值都是1000的整數倍
        }
        int alli = 0;
        for(j = 0; j < Y; j++)
        {
            M += alli;
            int P = M / 1000;//債券的面值都是1000的整數倍
            memset(f, 0, sizeof(f));
            for(i = 1; i <= d; i++)
                for(k = bd[i].w; k <= P; k++)
                    f[k] = Max(f[k], f[k - bd[i].w] + bd[i].i);
            alli = f[P];    
        }
        M += alli;
        printf("%d\n", M);
    }
    //system("pause");
}

posted @ 2012-08-14 11:45 小鼠標 閱讀(221) | 評論 (0) | 編輯 收藏

poj3624--最赤裸的01背包

不多說了，最赤裸的01背包問題。
01背包壓縮的動態方程為f[v]=Max(f[v],f[v-Ci]+Wi)。
詳情參閱《背包九講》：http://wenku.baidu.com/view/519124da5022aaea998f0f22.html
以下是本題代碼：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 20000
#define LENN 4000
typedef struct 
{
    int w;
    int d;
}Charm;
int Max(int a, int b)
{
    if(a > b)
        return a;
    return b;
}
int main()
{
    int i, j;
    Charm cm[LENN];
    int N, M;
    int f[LEN];
    while(scanf("%d%d", &N, &M) != EOF)
    {
        for(i = 1; i <= N; i++)
            scanf("%d%d", &cm[i].w, &cm[i].d);
        memset(f, 0, sizeof(f));
        for(i = 1; i <= N; i++)
            for(j = M; j >= cm[i].w; j--)
                f[j] = Max(f[j], f[j - cm[i].w] + cm[i].d);
        printf("%d\n", f[M]);
    }
    //system("pause");
}

posted @ 2012-08-14 10:44 小鼠標 閱讀(352) | 評論 (0) | 編輯 收藏

zoj3157--逆序對

由于跟另外一題基本一樣，這里不多解釋了，請參閱：

http://m.shnenglu.com/hoolee/archive/2012/08/13/187069.html
以下是本題代碼：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 10100
typedef struct 
{
    double l;
    double r;
}Node;
typedef struct 
{
    int x0;
    int y0;
    int x1;
    int y1;
}Line;
Line lin[LEN];
Node nd[LEN];
long long count;
int cmp(const void *a, const void *b)
{
    Node *a0 = (Node*)a;
    Node *b0 = (Node*)b;
    if(fabs(a0 -> l - b0 -> l) > 0.000000001)
        return a0 -> l > b0 -> l ? 1 : -1;
    else
        return a0 -> r > b0 -> r ? 1 : -1;
}
void Merge(Node *nd, int f, int m, int r)
{
    int i, j, k;
    Node *b = (Node*)malloc(sizeof(Node) * (r - f + 3));
    i = f;
    j = m + 1;
    k = 0;
    while(i <= m && j <= r)//merge
    {
        if(nd[i].r <= nd[j].r)
        {
            b[k++] = nd[i++];
            if(k + f > i)
                count += k + f - i;
        }
        
        else
            b[k++] = nd[j++];
    }
    while(i <= m)
    {
        b[k++] = nd[i++];
        if(k + f > i)
            count += k + f - i;
    }
    while(j <= r)
        b[k++] = nd[j++];
    for(i = f; i <= r; i++)//copy
        nd[i] = b[i - f];
    free(b);
}
void MgSort(Node *nd, int f, int r)
{
    if(f < r)
    {
        int m = (f + r) / 2;
        MgSort(nd, f, m);
        MgSort(nd, m + 1, r);
        Merge(nd, f, m, r);
    }
}
int main()
{
    int i, j;
    int n;
    double x0, y0, x1, y1;
    double k, t;
    double l, r;
    while(scanf("%d", &n) != EOF)
    {
        for(i = 0; i < n; i++)
        {
            scanf("%d%d%d%d", &lin[i].x0, &lin[i].y0, &lin[i].x1, &lin[i].y1);
        }
        scanf("%lf%lf", &l, &r);
        for(i = 0; i < n; i++)
        {
            k = 1.0 * (lin[i].y1 - lin[i].y0) / (lin[i].x1 - lin[i].x0);
            nd[i].l = k * (l - lin[i].x0) + lin[i].y0;
            nd[i].r = k * (r - lin[i].x0) + lin[i].y0;
        }
        qsort(nd, n, sizeof(Node), cmp);
        count = 0;
        MgSort(nd, 0, n - 1);
        printf("%lld\n", count);    
    }
    //system("pause");
}

posted @ 2012-08-13 15:12 小鼠標 閱讀(244) | 評論 (0) | 編輯 收藏

zoj3129--逆序對

題意描述：
求若干條線段交叉點的個數。題目保證不會有兩條以上的線段交與一點。
乍一看還以為是計算幾何的東西，其實不然，題目的條件限制使得這一題很簡單。我們把題目描述的地圖想象為笛卡爾坐標系上的點，可以規定，兩邊岸上的點都有相同的x值（分別為x0，x1且x0<x1），這樣，如果x0，x1所夾范圍內存在相交的兩條線段l1、l2的話，假設他們與x0，x1交點的y值分別為l1y0,l1y1和l2y0,l2y1，那么這兩條線段必須滿足以下簡單條件：(l1y0-l2y0)*(l1y1-l2y1)<0。也就是說，在直線x0上和x1上，l1、l2的y值大小順序是相反的，這讓我們聯想到了逆序對。
具體做法是：
先將每條線段按x0對應的y值排序（我稱之為第一次排序），然后根據x1對應的y值求出逆序對的個數，既是交叉點的個數。求逆序對的方法最直接的就是在冒泡排序是記錄交換的次數，不過這樣會超時，改進的算法是利用歸并排序，在每次歸并的時候統計逆序對個數（注意兩個數相等的情況，當兩數相等時它們不是逆序對）。
注意：在第一次排序中，因為不同線段的y值可能是相等的，這種情況下我們要依據x1對應的y值排序。忽略這種情況會導致計算的逆序對個數增多。
逆序對參閱：http://m.shnenglu.com/hoolee/archive/2012/07/18/184090.html
做的好艱辛，感謝冰冰學長。
以下是本題代碼：

#include<stdio.h>
#include<stdlib.h>
#define LEN 1010000
typedef struct 
{
    int e;
    int w;
}Road;
long long count;
Road rd[LEN];
int cmp(const void *a, const void *b)
{
    Road *a0 = (Road*)a;
    Road *b0 = (Road*)b;
    if(a0 -> e != b0 -> e)
        return a0 -> e > b0 -> e ? 1 : -1;
    else
        return a0 -> w > b0 -> w ? 1 : -1;
}
void Merge(Road *rd, int f, int m, int r)
{
    int i, j;
    Road *b = (Road*)malloc(sizeof(Road) * (r - f + 3));
    i = f;
    j = m + 1;
    int k = 0;
    while(i <= m && j <= r)
    {
        if(rd[i].w > rd[j].w)
            b[k++] = rd[j++];
        else
        {
            b[k++] = rd[i++];
            if(k + f > i)
                count += (k + f - i);
        }
    }
    while(i <= m)
    {
        b[k++] = rd[i++];
        if(k + f > i)
            count += (k + f - i);
    }
    while(j <= r)
        b[k++] = rd[j++];
    for(i = f; i <= r; i++)
        rd[i] = b[i - f];
    free(b);
}
void MgSort(Road *rd, int f, int r)
{
    if(f < r)
    {
        int m = (f + r) / 2;
        MgSort(rd, f, m);
        MgSort(rd, m + 1, r);
        Merge(rd, f, m, r);
    }
}
int main()
{
    int i, j, k;
    int N, M, K;
    int T;
    scanf("%d", &T);
    for(k = 1; k <= T; k++)
    {
        scanf("%d%d%d", &N, &M, &K);
        for(i = 0; i < K; i++)
            scanf("%d%d", &rd[i].e, &rd[i].w);
        qsort(rd, K, sizeof(Road), cmp);
        count = 0;
        MgSort(rd, 0, K - 1);
        printf("Test case %d: %lld\n", k, count);
    }
    //system("pause");
    return 0;
}

posted @ 2012-08-13 15:04 小鼠標 閱讀(1318) | 評論 (1) | 編輯 收藏

poj2389--大數乘法C和Java實現

大整數的乘法。假設求a*b，做法是將b的每一位與a相乘后再求和，注意b的不同位權值是不一樣的。
以下是本題代碼：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100
void Out(char *s)
{
    for(int i = 0; i < 10; i++)
        printf("%d", s[i]);
    putchar(10);
}
void Add(char *num1, char *num2)
{
    int i, j;
    for(i = 0; i < LEN; i++)
        num1[i] += num2[i];
    int t = 0;
    int t2;
    for(i = 0; i < LEN; i++)
    {
        t2 = num1[i] + t;
        t = t2 / 10;
        num1[i] = t2 % 10;
    }
}
void Multi(char *num1, int n, int w)
{//num1與n相乘，n的權重為10^(w-1)
    int i, j;
    char c;
    int len = LEN;
    while(num1[--len] == 0 && len > 0);
    for(i = len; i >= 0; i--)//move 
        num1[w - 1 + i] = num1[i];
    for(i = 0; i < w - 1; i++)
        num1[i] = 0;
    for(i = 0; i < LEN; i++)//multiply
        num1[i] *= n;
    int t = 0;
    int t2;
    for(i = 0; i < LEN; i++)//carry bit
    {
        t2 = num1[i] + t;
        t = t2 / 10;
        num1[i] = t2 % 10;
    }
    
}
void Reverse(char *s)
{
    int len = strlen(s);
    for(int i = 0; i < len / 2; i++)
    {
        char c = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = c;
    }
}
void ToNum(char *s)
{
    int len = strlen(s);
    for(int i = 0; i < len; i++)
        s[i] -= '0';
}
void Copy(char *t, char *f)
{
    for(int i = 0; i < LEN; i++)
        t[i] = f[i];
}
char A[LEN];//最終結果
char B[LEN];//乘數
char C[LEN];//乘數
char D[LEN];
/*
*獲取C[]的每一位與B[]相乘，結果存在D[]中，
*并不斷將D[]加到A[]上，最后A[]中存的就是結果
*/
int main()
{
    int i, j;
    gets(B);
    gets(C);
    int lenc = strlen(C);
    Reverse(B);
    Reverse(C);
    ToNum(B);
    ToNum(C);
    int w = 1;
    for(i = 0; i < lenc; i++)
    {
        Copy(D, B);
        Multi(D, C[i], i + 1);
        Add(A, D);
    }
    i = LEN;
    while(A[--i] == 0 && i > 0);
    for(; i >= 0; i--)
        printf("%d", A[i]);
    putchar(10);
    //system("pause");
}

下面是java版本的代碼，突然感覺用C寫大數純粹是自虐

import java.math.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        BigInteger b1 = new BigInteger(s1);
        BigInteger b2 = new BigInteger(s2);
        BigInteger b3 = b2.multiply(b1);
        System.out.println(b3);
    }

}

啊。。。

posted @ 2012-08-12 11:16 小鼠標 閱讀(525) | 評論 (0) | 編輯 收藏

僅列出標題

共13頁: First 2 3 4 5 6 7 8 9 10 Last