摘要: 下面我先说以下拓扑排序：
严蔚敏《数据结构》上的定义是：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
直观的说偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。
拓扑排序的具体做法是：
1.在有向图中选择一个没有前驱（入度为0）的顶点，输出
2.从图中删除该顶点和所有以它为尾的弧，并更新相关点的入度
3.重复1，2步，直到所有顶点都被输出，或者发现图中存在回路。  阅读全文 题意描述：
有几种面额固定的硬币，每种面额的硬币都有无数张。给你一定的金额，问总共有多少种找零方案。
完全背包问题，动态方程为：f[j] += f[j - mny[i]];
myi[i]表示第i种硬币的面值，f[j]表示数额为j的找零方案。
表示对完全背包的动态方程不甚理解，希望大神不惜指点。。
以下是本题代码：
题意描述：
给定一定数量的不同面值的钞票，输出由这些钞票组成的不超过出款上限（题目中的cash）的最大金额。
01背包问题，请参阅：http://www.cppblog.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 小鼠标 阅读(1536) | 评论 (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 小鼠标 阅读(210) | 评论 (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 小鼠标 阅读(330) | 评论 (0) | 编辑 收藏

zoj3157--逆序对

由于跟另外一题基本一样，这里不多解释了，请参阅：

http://www.cppblog.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 小鼠标 阅读(231) | 评论 (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://www.cppblog.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 小鼠标 阅读(1304) | 评论 (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 小鼠标 阅读(462) | 评论 (0) | 编辑 收藏

仅列出标题

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