2955专题

HDU 2955 Robberies （转化概率-01背包）

【题目链接】：click here~~ 代码： /** Problem: HDU No.2955* Running time: 46MS* Complier: G++* Author: ACM_herongwei* Create Time: 15:01 2015/9/9 星期三* zeroonebags* 用成功逃走的概率当做价值！银行的总钱数当做背包容量！单个银行的钱数体积

poj 2955(区间DP)

Language:Default Brackets Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2394 Accepted: 1233 Description We give the following inductive definition of a “regular bracke

POJ 2955 区间DP

求最多能匹配的括号数*2 #include "stdio.h"#include "string.h"int max(int a,int b){if (a<b) return b;else return a;}int judge(char a,char b){if (a=='(' && b==')') return 1;if (a=='[' && b==']') return 1

HDU-2955 Robberies 01背包 + 概率

题目链接刚开始以为概率就2位小数乘100来做WA 看了讨论区恍然大悟。用成功逃走的概率当做价值！银行的总钱数当做背包容量！ #include <stdio.h>#include <string.h>#include <iostream>#include<functional>#include <queue>#include <string>#include

HUD 2955 Robberies [0-1背包的简单转化]

/*Hud 2955 Robberies简单的0-1背包转换.由此题，抽象的事物也可以相当形象的解释.形象的解释，看以下注释.*/#include<stdio.h>#include<string.h>#define max(a,b) a>b?a:bmain(){int T;scanf("%d",&T);while(T--){int i,n,v[105],V=0;double p,w[1

HDOJ 2955

这道背包题和我们常见的背包题有所不同。如果根据以前做背包的惯性思维和题中数据的迷惑，会把概率乘以100来当作容量。但是经测试是不行的。我们不妨换种思路，看做DAG上的DP思想。将所有有可能达到的钱的最大“逃跑”概率算出来，最后再将能够达到的最大的钱输出。而能不能够达到这个可以将所有除0以外的值初始化为0.意为逃跑的概率为0。 #include<cstdio>#include<cstring>

hdu 2955 dp(0,1背包) Robberies

这个，刚开始，想的是所有人的想法，把概率乘到整数，然后0,1背包。但是，想着要乘几位，于是看了下别人的。。。没想到，是反过来，把抢的钱看成背包,把逃跑率看成价值。 dp[i][j]表示抢第i家银行要抢j的钱能逃跑的最大概率。当money[i]<=j时，dp[i][j]=max(dp[i-1][j],dp[i-1][j-money[i]]*p[i]); 这里因为是概率问题，所以是相乘

POJ 2955 Brackets (区间dp 括号匹配)

Brackets Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 3951 Accepted: 2078 Description We give the following inductive definition of a “regular brackets” sequence: the empt

HDU 2955 Robberies（概率DP）

思路：直接令dp[i][j]表示抢前i个银行，抢了j块钱不被抓的概率是多少，然后就和01背包一样转移就可以了 #include<bits/stdc++.h>using namespace std;double dp[10000+5];double p[105];int w[105];int main(){int T;scanf("%d",&T);while(T--){mem

（POJ 2955）Brackets 区间DP 最大括号匹配

Brackets Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6647 Accepted: 3577 Description We give the following inductive definition of a “regular brackets” sequence: the empty sequence

POJ 2955 Brackets POJ 1505 Copying Books POJ 1651 Multiplication Puzzle(初级区间DP)

POJ 2955 Brackets 题目大意在给定字符串中有多少个可匹配括号，()和[]为可匹配。解题思路 dp[i][j]代表i~j有多少个可匹配的字符串。转移方程： 1、dp[i][j]=dp[i+1][j-1]+2，当i,j位置组成可匹配括号； 2、枚举分割点k (i≤k<j) (i \le k<j) ：dp[i][j]=max(dp[i][j],dp[i][k]+dp

poj 2955 Brackets(区间DP，经典问题)求有规律的括号的最大长度

1、http://poj.org/problem?id=2955 2、题目大意给出一个只包含()[]的字符序列，求出该字符序列中有规律的符号序列的最长长度有规律的序列要求如下： the empty sequence is a regular brackets sequence,if s is a regular brackets sequence, then (s) and [s] a