51nod-1031 骨牌覆盖

发表于 动态规划 分类,标签:
 在2*N的一个长方形方格中,用一个1*2的骨牌排满方格。问有多少种不同的排列方法。例如:2*3的方格,共有3种不同的排法。(由于方案的数量巨大,只输出Mod10^9+7的结果)Input输入N(N <= 1000)Output输出数量 Mod 10^9 + 7Input示例3Output示例3思路:斐波纳契数列。。。代码:#include<iostream>#include<algorithm>#include<math.h>#include<stdio.h>#include <string.h>#define LL long long#define MAX&nb...

51nod-1050 循环数组最大子段和

发表于 动态规划 分类,标签:
 N个整数组成的循环序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列)。当所给的整数均为负数时和为0。例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。Input第1行:整数序列的长度N(2 <= N <= 50000)第2 - N+1行:N个整数 (-10^9 <= S[i] <= 10^9)Output输出循环数组的最大子段和。Input示例6-211-413-5-2Output示例20思路:整个数组可以形成一个环,那么...

51nod-1042 数字0-9的数量

发表于 动态规划 分类,标签:
 给出一段区间a-b,统计这个区间内0-9出现的次数。比如10-19,1出现11次(10,11,12,13,14,15,16,17,18,19,其中11包括2个1),其余数字各出现1次。Input两个数a,b(1 <= a <= b <= 10^18)Output输出共10行,分别是0-9出现的次数Input示例10 19Output示例11111111111思路:跟51nod1009题上类似,然后特殊处理0就行。代码如下,直接从1009题代码修改来的没优化。。。#include<bits/stdc++.h>using namespace std;#define LL long long...

51nod-1009 数字1的数量

发表于 动态规划 分类,标签:
 给定一个十进制正整数N,写下从1开始,到N的所有正数,计算出其中出现所有1的个数。例如:n=12,包含了5个1。1,10,12共包含3个1,11包含2个1,总共5个1。Input输入N(1 <= N <= 10^9)Output输出包含1的个数Input示例12Output示例5思路:对于数N,可以将其划分为三个部分,n-k(i)-m,  k(i)为N的第i为数字,n为第i位数前面部分组成的数,m为第i位数后面部分组成的数。第i位上1的个数计算,p为10^(len(m)):若k(i)大于1:(n+1)*p;若k(i)等于1:n*p+m+1;若k(i)小于1:n*p;代码#include<bits/stdc++.h>using namespace std;#def...

51nod-1094 和为k的连续区间

发表于 动态规划 分类,标签:
 一整数数列a1,a2,...,an(有正有负),以及另一个整数k,求一个区间[i,j],(1<=i<=j<=n),使得a[i]+...+a[j]=k。Input第1行:2个数N,K。N为数列的长度。K为需要求的和。(2 <= N <= 10000,-10^9 <= K <= 10^9)第2 - N + 1行:A[i](-10^9 <= A[i] <= 10^9)。Output如果没有这样的序列输出No Solution。输出2个数i, j,分别是区间的起始和结束位置。如果存在多个,输出i最小的。如果i相等,...

51nod-1133 不重叠的线段

发表于 动态规划 分类,标签:
 X轴上有N条线段,每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。(注:起点或终点重叠,不算重叠)。例如:[15][23][36],可以选[23][36],这2条线段互不重叠。Input第1行:1个数N,线段的数量(2 <= N <= 10000)第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)Output输出最多可以选择的线段数量。Input示例31 52 33 6Output示例2思路:按线段结束点从小到大排序,然后贪心。。代码:#include<bits/stdc++.h>using ...

51nod-1091 线段的重叠

发表于 动态规划 分类,标签:
 X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[1020]和[1225]的重叠部分为[1220]。给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。Input第1行:线段的数量N(2 <= N <= 50000)。第2 - N + 1行:每行2个数,线段的起点和终点。(0 <= s , e <= 10^9)Output输出最长重复区间的长度。Input示例51 52 42 83 77 9Output示例4思路:按线段起点从小到大排序,然后贪心。代码:...

51nod-1279 扔盘子

发表于 动态规划 分类,标签:
 有一口井,井的高度为N,每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘,如果圆盘的宽度大于井在某个高度的宽度,则圆盘被卡住(恰好等于的话会下去)。盘子有几种命运:1、掉到井底。2、被卡住。3、落到别的盘子上方。盘子的高度也是单位高度。给定井的宽度和每个盘子的宽度,求最终落到井内的盘子数量。如图井和盘子信息如下:井:5643623盘子:23524最终有4个盘子落在井内。本题由 @javaman 翻译。Input第1行:2个数N, M中间用空格分隔,N为井的深度,M为盘子的数量(1 <= N, M <= 50000)。第2 - N + 1行,每行1个数,对应井的宽度Wi(1 <= Wi &...

51nod-1432 独木舟

发表于 动态规划 分类,标签:
 n个人,已知每个人体重。独木舟承重固定,每只独木舟最多坐两个人,可以坐一个人或者两个人。显然要求总重量不超过独木舟承重,假设每个人体重也不超过独木舟承重,问最少需要几只独木舟?Input第一行包含两个正整数n (0<n<=10000)和m (0<m<=2000000000),表示人数和独木舟的承重。接下来n行,每行一个正整数,表示每个人的体重。体重不超过1000000000,并且每个人的体重不超过m。Output一行一个整数表示最少需要的独木舟数。Input示例3 6123Output示例2思路:因为最多只能坐两个人所以只需要看最小的和最大的能否坐在一起,不能就让最大的坐,将最大的去掉后再重复上述步骤。代码:#include<bits/stdc++.h>//#include<stdio....

51nod-1413 权势二进制

发表于 动态规划 分类,标签:
 一个十进制整数被叫做权势二进制,当他的十进制表示的时候只由0或1组成。例如0,1,101,110011都是权势二进制而2,12,900不是。当给定一个n的时候,计算一下最少要多少个权势二进制相加才能得到n。Input单组测试数据。第一行给出一个整数n (1<=n<=1,000,000)Output输出答案占一行。Input示例9Output示例9思路:其实只要比较数各个位数,找出其中最大的输出就行,因为如:321=111+110+100。代码#include<bits/stdc++.h>using namespace std;#define LL long long#define INF 0x3f3f3f3f#define MAX ...