piggydog-CSDN博客

原创 FAFU-OJ 1408 摆花

题目连接：http://acm.fafu.edu.cn/problem.php?id=1408方法一：开一个数组char s[1000][1000]保存图形，再打印。#include char s[999][999];int main(){ int i,j,q,n; scanf("%d",&n); char c = 'A' + (n+1)/2%26; int t

2013-12-12 19:41:11 889

原创 FAFU-OJ 1004 大数乘积

直接上源代码： #include #include #define N 200char s[N] = {0}, c[N] = {0};int sn[N], sc[N], cn[N];int monitor = 0;int last = 0;void cheng(int y, int j) //进行乘法运算{ int i = j; while(sn[i-j]

2013-08-10 12:35:54 1012

原创 FAFU-OJ 1002 简单吗？

直接上源代码： #include #define N 150int a[N];int b[N];int c[N];void cheng(__int64 x, __int64 y) //进行大数乘法运算{ int i, j; i = 0; while(x > 0) { a[i] = x % 10; x /= 10; i++; } i = 0; wh

2013-08-10 12:28:52 846

转载 P11: 背包问题的搜索解法

《背包问题九讲》的本意是将背包问题作为动态规划问题中的一类进行讲解。但鉴于的确有一些背包问题只能用搜索来解，所以这里也对用搜索解背包问题做简单介绍。大部分以01背包为例，其它的应该可以触类旁通。简单的深搜对于01背包问题，简单的深搜的复杂度是O(2^N)。就是枚举出所有2^N种将物品放入背包的方案，然后找最优解。基本框架如下：procedure SearchPack(i,cur_v,c

2013-08-05 12:04:24 863

转载附：USACO中的背包问题

题目列表Inflate (+) （基本01背包）Stamps (+)(!) （对初学者有一定挑战性）MoneyNuggetsSubsetsRockers (+) （另一类有趣的“二维”背包问题）Milk4 (!) （很怪的背包问题问法，较难用纯DP求解）题目简解以下文字来自我所撰的《USACO心得》一文，该文的完整版本，包括我的程序，可在DD的USACO征程中找到。In

2013-08-05 12:03:38 848

转载 P09: 背包问题问法的变化

以上涉及的各种背包问题都是要求在背包容量（费用）的限制下求可以取到的最大价值，但背包问题还有很多种灵活的问法，在这里值得提一下。但是我认为，只要深入理解了求背包问题最大价值的方法，即使问法变化了，也是不难想出算法的。例如，求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值（f数组）之后得到。还有，如果要求的是“总价值最小”“总件数最小

2013-08-05 12:02:16 851

转载 P08: 泛化物品

定义考虑这样一种物品，它并没有固定的费用和价值，而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义之。在背包容量为V的背包问题中，泛化物品是一个定义域为0..V中的整数的函数h，当分配给它的费用为v时，能得到的价值就是h(v)。这个定义有一点点抽象，另一种理解是一个泛化物品就是一个数组h[0..V]，给它费用v，可得到价值h[V]。一个费用为c价值为w的物品

2013-08-05 12:01:16 561

转载 P07: 有依赖的背包问题

简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。算法这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有

2013-08-05 12:00:08 662

转载贪心算法

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下： 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3

2013-08-05 11:54:53 643

转载逆波兰表达式（后缀表达式）2

逆波兰表达式逆波兰表达式又叫做后缀表达式。在通常的表达式中，运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家 J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构

2013-08-05 11:49:17 741

转载 P06: 分组的背包问题

问题有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。算法这个问题变成了每组物品有若干种策略：是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有：f[k][v]=m

2013-08-05 11:27:21 601

转载 P05：二维费用的背包问题

问题二维费用的背包问题是指：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值（背包容量）。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。算法费用加了一维，只需状态也加一维即可。设f[i]

2013-08-05 11:26:25 753

转载 P04: 混合三种背包问题

问题如果将P01、P02、P03混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？01背包与完全背包的混合考虑到在P01和P02中给出的伪代码只有一处不同，故如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环

2013-08-05 11:25:19 478

转载 P03: 多重背包问题

题目有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本算法这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背

2013-08-05 11:24:21 457

原创 P02: 完全背包问题

题目有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。基本思路这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f

2013-08-05 11:23:34 483

原创 P01: 01背包问题

题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i

2013-08-05 11:20:45 663

转载逆波兰表达式总结

将一个中序表达式转化成为逆波兰表达式的方法其实很简单，也是一个成型的算法。通过逆波兰表达式求一个计算式子的值，也是很简单的，只要遇到过会用就行了。1、将一个中序表达式转化成为逆波兰表达式。首先维护的是两个栈，我们这里暂且称为S1和S2，S1中的结果最后存的就是逆波兰表达式，S2中将用于暂时存放运算符并且在最终形成逆波兰表达式的时候，该栈是会清空的。下面我们看看怎样具体的形成逆

2013-08-05 11:18:50 1155

原创 FAFU-OJ 1354 解方程

今天花了半个早上A出来的一道解一元一次方程的题目，题目链接为http://acm.fafu.edu.cn/problem.php?id=1354解题报告： 1、先把等号找出，左右隔开2、扫描含有未知字母，统计字母的系数3、剩余的数存入数组，左边+左边，右边+右边4、算出结果包含函数：1、读入左侧数字的函数，2、读入右侧数字的函数，3、删除刚刚被读过的数

2013-08-04 13:12:49 1036

原创 FAFU-OJ 1329 IP test

这道题的链接是： http://acm.fafu.edu.cn/problem.php?id=1329我想说，虽然题意很简单。但是还要注意考虑周到真的不容易。比如IP地址为1.3.4.2这样显然是正确的，我们用眼睛一看就知道。但是我们要清楚，IP地址有以下特点：1、必须分成4快；2、必须有3个‘.’且两两不相邻；3、每部分的数字必须在0-255之间；4、不能有除了数字和点以外的

2013-07-29 15:57:55 743

原创 FAFU-OJ 1328 Free Cash

链接题目地址： http://acm.fafu.edu.cn/problem.php?id=1328题意其实很简单，就是理解为搜寻被某个二维数组被记录了几次。 #include #include #include #include using namespace std;const int maxn=100;int a[maxn][maxn];int max(int

2013-07-27 12:16:50 946

原创 FAFU-OJ 1224 Ping

http://acm.fafu.edu.cn/problem.php?id=1224上面是网站链接地址；PingTime Limit:1000MSMemory Limit:65536KBTotal Submissions:28Accepted:10ShareDescription: 在操

2013-07-26 22:54:18 843

原创 FAFU-OJ 1338 素数难题代码

#include #include #include #define N 1230 //一万以内素数个数int main(){ int n; int s[N]; int c[10000] = {0}; //c[i]表示连续素数和为i的情况有多少种 int a, flag; int i, j, x; int point = 2; int

2013-07-25 10:48:18 867

A+C=V