当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] poj 1952 BUY LOW, BUY LOWER 最长下降子序列计数

    题意: 给n个数,求它的最长下降子序列长度和数量。 分析: dp,计数的时候要避免重复计数。 代码: //poj1952 //sep9 #include<iostream> usingnamespacestd; constintmaxN=5012; inta[maxN]; intdp[...

    93
    热度
  • [综合] poj 2215 Parliament 二维区间和

    题意: 给一个二维数组,查询(r1,s1),(r2,s2)确定的矩形中所有数的和。 分析: dp水题,sum[r][s]表示从(0,0)到(r,s)确定的矩形中所有数的和。 代码: //poj2215 //sep9 #include<iostream> usingnamespacest...

    29
    热度
  • [综合] poj 2584 T-Shirt Gumbo 二分图多重匹配

    题意: 有x个选手,每个选手有能接受的T恤号码,每种号码的T恤都有一定的数量,问是否有一种分配方案能让所有的选手都满意。 分析; 二分图的多重匹配问题,用匈牙利变形直接水。 代码: //poj2584 //sep9 #include<iostream> usingnamespacest...

    41
    热度
  • [综合] poj 2761 Feed the dogs 划分树

    题意: 给长度为n的数组和m个区间,求这m个区间中第k小的数。 分析: 数组静态,区间和k动态,划分树的定义题,上模板。 代码: //poj2761 //sep9 #include<iostream> #include<algorithm> usingnamespacest...

    92
    热度
  • [综合] poj 2785 4 Values whose Sum is 0 哈希

    题意: 给4个集合ABCD,问有多少种从中各取一个数和为0的方案。 分析: 枚举前两个数建哈希表,枚举后两个数查找即可。 代码: //poj2785 //sep9 #include<iostream> usingnamespacestd; constintmaxN=4012; cons...

    75
    热度
  • [综合] poj 2115 C Looooops 扩展欧几里得

    题意: 在while(x=a;x!=b;x+=c)statement;中,问statement会被执行多少次,计算在2^k下进行。 思路: 等价于计算同余式a+c*x=b(mod2^k)用扩展欧几里得算法。设g=gcd(a,b)在计算a*x+b*y=g过程中,x的结果可以用b/g调整,y的结果可以用...

    25
    热度
  • [综合] poj 2895 Best SMS to Type 模拟

    水题,直接贴代码。 //poj2895 //sep9 #include<iostream> usingnamespacestd; intmap[200][2]; chara[1024]; intmain() {map[''][0]=1,map[''][1]=1;map['A'][0]=...

    79
    热度
  • [综合] poj 3140 Contestants Division 树的遍历

    题意: 给一棵树,每个节点有一个值v,现在要去掉一条边,使分成的两棵树的v的和的差值最小。 分析: 水题,注意数据范围。 代码: //poj3140 //sep9 #include<iostream> usingnamespacestd; constintmaxN=200024; in...

    66
    热度
  • [综合] poj 3230 Travel 简单dp

    题意: 有n个城市,从城市i到城市j的花费为exp[i][j],有m天,第i天在城市j的收入为inc[i][j],每天可以选择留在当前城市或去下一个城市,问m天结束最多能有多少钱? 代码: 简单dp,dp[i][j]表示第i天结束在城市j能有多少钱。 代码: //poj3230 //sep9 #i...

    47
    热度
  • [综合] poj 3661 Running dp

    题意: 有n分钟时间,每分钟牛能跑d[i]路程,在每分钟,牛可以选择跑,这样疲劳度会+1,也可以选择不跑,这样疲劳度会-1(最少到0),问n分钟后疲劳度为0时最多能跑多远,注意牛要疲劳度为0才能继续跑。 分析: 设dp[i][j]表示i分钟结束奶牛疲劳度为j时能跑的最远距离,则转移有:dp[i-1]...

    79
    热度
  • [综合] poj 3646 The Dragon of Loowater 排序+贪心

    水题,直接贴代码。 //poj3646 //sep9 #include<iostream> #include<algorithm> usingnamespacestd; constintmaxN=20012; inta[maxN],b[maxN];intmain() {in...

    91
    热度
  • [综合] poj 3670 Eating Together dp

    dp水题,直接贴代码。 //poj3670 //sep9 #include<iostream> usingnamespacestd; constintmaxN=30024; intn; inta[maxN],b[maxN]; intdp[maxN][4];intsolve(inta[]...

    62
    热度
  • [综合] poj 2914 Minimum Cut 无向图最小边割

    题意: 求无向图的全局最小边割。 分析: stoer-wagner模板。 代码: //poj2914 //sep9 #include<iostream> usingnamespacestd; constintmaxN=512; intg[maxN][maxN]; intb[maxN],...

    99
    热度
  • [综合] poj 3204 Ikki's Story I - Road Reconstruction 最大流

    题意: 在有向流网络中求有多少条边满足增加其流量能增加总流。 分析: 先求最大流,然后从源汇点沿不满流边染色,边尾被源点染色,边头被汇点染色则计数。 代码: //poj3204 //sep9 #include<iostream> #include<queue> usingn...

    29
    热度
  • [综合] poj 2336 Ferry Loading II 贪心

    水题,直接贴代码。 //poj2336 //sep9 #include<iostream> usingnamespacestd; constintmaxN=1600; inta[maxN]; intmain() {intcases;scanf("%d",&cases);whil...

    12
    热度
  • [综合] poj 2837 Silver Matrix 不使用栈的深搜

    题意: 给定k,让构造一个2^k*2^k的矩阵,使得对任意i,第i行和第i列由1,2,...2^k-1这2^k-1个数组成。 分析: 很明显是个深搜题。设n=2^k,则搜素树高度(状态空间维度)为n,每个状态可扩展n个状态,复杂度n^n,大概是512^512。。。所以必须有强力的剪枝而且不要用递归去...

    83
    热度
  • [综合] poj 1695 Magazine Delivery dp

    题意: 有n个地方,每两个点之间需要的时间已知,现在有3辆车在地点1,要把杂志送到2,3...n,同一时刻只能有一辆车在走,且送到i之前必须送到i-1,求完成任务需要的最少时间。 分析: dp[a][[b][c]表示三辆车由近到远在a,b,c三个地方所要的最少时间。当n==6时,2,2,1,3,1,...

    33
    热度
  • [综合] poj 1149 PIGS 最大流

    题意: 有M个猪圈每个猪圈里初始时有若干头猪,开始时所有猪圈都是关闭的。依次来了N个顾客,每个顾客分别打开指定的几个猪圈,从中买若干头猪,每个顾客最多能买的猪数是确定的。每个顾客走后,他打开的那些猪圈中的猪可以自由流动,然后所有猪圈重新关上。 分析: 最大流,关键是处理顾客i买完猪后他打开的猪圈可以...

    36
    热度
  • [综合] poj 3051 Satellite Photographs dp水题

    水题,直接贴代码。 //poj3051 //sep9 #include<iostream> usingnamespacestd; charg[1024][128]; intdp[1024][128]; intw,h,ans; intsearch(intx,inty) {dp[x][y]...

    10
    热度
  • [综合] poj 1492 Up and Down Sequences 模拟计数

    水题,直接贴代码。 //poj1492 //sep9 #include<iostream> usingnamespacestd; inta[64]; intn; voiddeal() {intup=0,down=0,upSum=0,downSum=0; inti,j;for(i=1;i...

    86
    热度