DP

上一篇结尾用全期望公式把 \(V^\pi(s)\) 按"下一个 State"分组展开了。Markov Property 那篇讨论了为什么 Bellman Equation 需要 Markov Property 作为前提。 数学工具准备齐了，我打算正式跟一遍 Bellman Equation 的推导。

起因 # 继续跟着 MIT 6.S191 Lecture 5 学强化学习。上一篇理解了 Return、State Value Function \(V^\pi(s)\) 和 Action Value Function \(Q^\pi(s,a)\)。

题意： # 求n个串的最长公共子串，n<=10 思路： # 不会啊orz

http://poj.org/problem?id=1949 # 题意： # 有n个任务，第i个任务需要时间xi来完成，并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。

http://poj.org/problem?id=3249 题意： # 给一个DAG，现要从一条入度为0的点到一个出度为0的点，问最大点权和。 思路： # 其实比较容易想到搜…不过复杂度会炸？

题目链接 题意：给出n,p,q,r，以及n（1E5）个数，所有数的范围都是[-1E9,1E9]，现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. 思路：由于有正，有负，还有0.。。所以比最大子串之和要复杂一些。。。 dp[i].max表示到当前位置的最大乘积。

Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. 1[ 2 [0,0,0], 3 [0,1,0], 4 [0,0,0] 5] The total number of unique paths is 2. 题意：从左上到右下的方案数，有些点不能走。

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. 数字三角形。。。。从左上到右下问最短路径。。每次只能向下或者向右。。。 wa了一次。。。是因为边界值赋值成了0.。。求最短路径显然因为赋值成inf才对orz..果然傻了。。

2748: [HAOI2012]音量调节 # Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1814 Solved: 1148 [Submit][Status][Discuss] Description # 一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。 音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i首歌开始之前吉他手想要改变的音量是多少。 吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

1207: [HNOI2004]打鼹鼠 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2854 Solved: 1390 [Submit][Status][Discuss] Description # 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个nn的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个nn的网格。游戏开始时，你可以自由选定机器人的初始位置。现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

题目链接 题意：容量为V的背包，n个骨头，给出价值和体积，问最多能装多少价值的背包。 思路：01背包裸体。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年11月16日 星期三 15时14分36秒 4File Name :code/hdu/2602.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E3+7; 34int dp[N],value[N],cost[N]; 35int n,V; 36void solve(int v,int c) 37{ 38 for ( int i = V; i >= c; i --) 39 dp[i] = max(dp[i],dp[i-c]+v); 40} 41int main() 42{ 43 #ifndef ONLINE_JUDGE 44 freopen("code/in.txt","r",stdin); 45 #endif 46 int T; 47 cin>>T; 48 while (T--) 49 { 50 scanf("%d%d",&n,&V); 51 ms(dp,0); 52 for ( int i = 1 ;i <= n ; i++) scanf("%d",&value[i]); 53 for ( int i = 1; i <= n ; i++) scanf("%d",&cost[i]); 54 for ( int i = 1 ; i <= n ; i++) solve(value[i],cost[i]); 55 int ans = 0 ; 56 57 for ( int i = 0 ; i <= V ; i++) ans = max(ans,dp[i]); 58 printf("%d\n",ans); 59 } 60 61 #ifndef ONLINE_JUDGE 62 fclose(stdin); 63 #endif 64 return 0; 65}

hdu1864题目链接 题意：中文题目，不多说了。 思路：正解是01背包，呵呵呵。 出题人是傻逼吗？ 不给数据范围？ 以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？ 本来看到这题这么恶心时不打算写的…

题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。

题目链接 题意：给出n(n<=1E3)个字符，字符可能为’D’,‘I’,’?’，第i位对应的字符分别表示，第i位大于第i+1位，第i位小于第i+1位，或者不确定。

题目链接 题意：问长度为n的“波浪”型排列（即1..n每个数出现一次）有多少。波浪型的含义是，“高低高”或者“低高低” 思路：我们考虑当前已经知道i-1个数的波浪型的排列的方案数，那么当第i个数到来时，第i个数一定是最大的。

1009: [HNOI2008]GT考试 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description # 阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9)，他不希望准考证号上出现不吉利的数字。 他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为 0

题目链接 题意：问长度为n，每个位置由且仅有‘H’和’T’组成的序列中，至少有连续k个‘H’出现的方案数。 思路：不会做，参考了题解 不过没有完全搞懂。

题目链接 题意：给出一个n个数的排列，每次可以把一个数放到最前面或者最后面的位置，问至少要进行多少次操作才能使得数列升序。 思路：考虑不被移动的那些数，当把所有一定的数去掉以后，这些剩下的数一定是一段数值连续，位置递增的数。如果想要移动的数最少，俺么这串递增的数就尽可能长。

题目链接 题意： 给定两个序列，求它们的最长公共递增子序列的长度， 并且这个子序列的值是连续的 思路：以值为连续做入手点。 很显然个鬼咯 dp[a[i]]表示以a[i]结尾的最大长度。 dp[a[i]] = dp[a[i-1]] + 1 对于b序列一样。