给定一个物品集合s={1,2,…..,n},物品i具有重量wi和价值vi。背包能承受能承受的最大载重量不超过W。背包问题就是找到一个物品子集s‘属于s,使得maxEwi<=W。所谓01背包就是物品要么整个地选取,要么不取。
首先我们先要肯定一件事,假设子问题(i,w)的最优装载中含有物品i,则其中的子问题(i-1,w-wi)的装载方案也一定是最优的。
证明:(反证法)假设子问题(i-1,w-wi)的装载方案p不是最优的,则有一个更优的装载方案p’,将p’替换p然后在加上物品i将会比原来的最优装载价值最大,与假设矛盾。
现设定一个数组v[i,w](i代表第几个物品,w代表i物体的[……]

继续阅读

link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=417#problem/S
http://acm.hdu.edu.cn/showproblem.php?pid=2844
题目大意:有n个物品,每个物品的价值为[i],meige物品的数量
为c[i],问用所有的硬币能够在m的范围内,最多可以组成多少组不同的值。
典型的多重背包问题(应该也可以用母函数做,不过不是很会),背包九讲上有具体解析
下面代码留着当模板,哦吼吼吼~~~~
code:

#include <stdio.h>
#inclu[……]

继续阅读

Description

农民JOHN以拥有世界上最健康的奶牛为骄傲。他知道每种饲料中所包含的的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛,以保持他们的健康,使喂给牛的饲料的种数最少。 给出牛所需的最低的维他命,输出喂给牛需要哪些种类的饲料,且所需的种类数最少。

Input

第1行:一个整数V(1<=V<=25),表示需要的维他命的种类数。 第2行:V个整数(1<=每个数<=1000),表示牛每天需要的维他命的最小量。 第3行:一个整数G(1<=G<=15),表示可用来喂牛的饲料的数量。下面G行,第i行表示编号为i饲料包含的各种维他命的量的多少[……]

继续阅读

Description

一个等差数列是一个能表示成a, a+b, a+2b,…, a+nb (n=0,1,2,3,…)的数列。 在这个问题中a是一个非负的整数,b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2+q^2的数的集合)S中长度为n的等差数列。

Input

第一行: N(3<= N<=25),要找的等差数列的长度。 第二行: M(1<= M<=250),搜索双平方数的上界0 <= p,q <= M。

Output

如果没有找到数列,输出`NONE’。 如果找到了,输出一行或多行, 每行由二个整数组成:a,[……]

继续阅读

Description

输入一个自然数N  请写一个程序来增序输出分母小于等于N的既约真分数

Input

单独的一行 一个自然数N(1..160)

Output

每个分数单独占一行

Sample Input

5

Sample Output

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

解题思路:这题题意清晰明了,只是这个排序问题让我纠结了long long time;最后好不容易有点小小的思路,死在qsort上,我就不明白了,为什么用sort就可以,用qsort就错呢,又没有相同的值,所以应该无所谓稳定排序以及不[……]

继续阅读

http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=397#problem/D
这题思路很简单,只要注意单位的处理就好了。判断是哪种情况的是根据“P=”  “U=”  “I=”区分的。每一次输出结束都要再输出一个空行,我开始做了n次
总是wrong,哪里找不出原因,最后把别人的代码运行发现自己的输出少了一个空行。
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int main()
{
    char c[6][10000]={0},s[10000[......]

继续阅读

Description

排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌序的时候。 在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。 写一个程序计算出,给定的一个1,2,3组成的数字序列,排成升序所需的最少交换次数。

Input

Line 1: N (1 <= N <= 1000) Lines 2-N+1: 每行一个数字,共N行。(1..3)

Output

共一行,一个数字。表示排成升序所需的最少交换次数。

Sample Input

9
2
2
1
3
3
3
2[......]

继续阅读

Description

下面是一个乘法竖式,如果用我们给定的那n个数字来取代*,可以使式子成立的话,我们就叫这个式子牛式。

      * * *
   x    * *
    -------
      * * *
    * * *
    -------
    * * * *

数字只能取代*,当然第一位不能为0,况且给定的数字里不包括0。

注意一下在美国的学校中教的“部分乘积”,第一部分乘积是第二个数的个位和第一个数的积,第二部分乘积是第二个数的十位和第一个数的乘积.

写一个程序找出所有的牛式。

Input

Line 1:数字的个数n。 Line 2[……]

继续阅读

Description

在威斯康辛州牛大农场经营者之中,都习惯于请会计部门用连续数字给母牛打上烙印。但是,母牛用手机时并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴,而不是用像这个的语句”C’mon, #4734, get along.”。

请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。因为母牛们现在都有手机了,使用那标准的按键的排布来把将数目翻译为文 字:( 除了 “Q” 和 “Z”) 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S

可接[……]

继续阅读

题意:给定一个图,无向,每条路有时间花费,每个地点有一个value;

求在给定的时间内得到的最大value

输入:

n:顶点数

ui  vi  ti :第i条路的起点,终点,时间

k m:开始点 给定时间

输出:

最大value

 

据说是树形dp!

树形dp?啥玩意儿?

反正我自己做出来了!

嗯,如果是树形dp的话,也做个纪念吧!

废话不多了,下面是我的代码:
#include<stdio.h>
#include<stdlib.h>
#include<memory.h&[……]

继续阅读

题目很好懂,数据量很大,把两个循环合并都能省不少时间!

不过我没试过用普通的数组,估计会超时!

据说用dp+线段树;

嗯,我自己写了一个,确实没那么难!

不过用线段树时,要搞清楚父节点存什么!

在此纪念我的第一道线段树!!!

下面是我的代码:

#include<stdio.h>
#include<memory.h>
#define intt long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
#define MAX 50005
#[……]

继续阅读

比赛链接:http://acm.csu.edu.cn/OnlineJudge/contest.php?cid=2024

A、逆元
题目要求:给定正整数x,y,求最小的正整数z使得x*z mod y = 1。
输入:x,y(2<=x,y<10^6)
输出:z或No

解题思路:因为y值不是很大,所以我就用暴力求解,一个for循环解决

#include <stdio.h>

#define intt long long

void solve(intt x,intt y){
    intt i;
    if(x%y==0){
  [……]

继续阅读

ZOJ2110-Tempter of the Bone(HDU1010)
题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2110
题意描述:给一幅地图,按要求从一个点到另一个点,且时间恰好等于给出的时间、、
题意分析:深搜吧、、、啊,纠结,输出的NO不小心写成No了,没发现,调了好久,还拿以前写的程序对照,然后改了很久、、、啊…………
详细代码解释:http://user.qzone.qq.com/1156638549/infocenter#!app=2&via=QZ.HashRefresh&[……]

继续阅读

A、Magic Number
题目大意:一个数y能够被称为Magic Number需满足对于任意正整数x,将y放在x的右边,构成新数z,满足z%y==0.
输入:m,n
输出:m与n之间Magic Number数的个数(包含m和n)
解题思路:打部分表之后找规律,在10以内满足条件的为:1,2,5;在10~100之间,满足条件的为10,20,25,50;在100~1000之间,满足条件的为100,125,200,250,500;在这之后的每一个10倍均有5个数满足条件。

#include <stdio.h>
#define intt  long long
in[……]

继续阅读