poj 1651题目链接 题意：n个数，删掉a[i]的得分是a[i]*a[i-1]*a[i+1]，两个端点的不允许删。问删完n-2个数得到的最小分数是多少。 思路：能想到设计状态dp[i][j]表示区间[i,j]的最小分数。然后就没思路了。 T T 参考了几篇题解，思路大概是，枚举最后剩下的那个数。 **对于一个区间(l, r),如果最后删除的是k位置的数的话，将得到a[l]*a[k]*a[r]分，而要得到这个情况的前提是吧区间(l, k) 和(k, r)的中间数字删掉所以的转移方程是** DP(l, r) = DP(l, k) + DP(k, r) + a[l]*a[k]*a[r]; 以及。。。初始化又想错了。。。 要注意。。初始 …

poj 3280 题目链接 题意：一个字符串，给出添加一个字符或者删掉该字符的花费，问最小的话费使得字符串变成回文串。 思路：dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。 这个可以想到。。dp[i][j] = dp[i+1][j-1] (a[i]==a[j])这个也可以想到。。。 增加和删除是等价的，所以取小的那个代价就行。。这个我也想到了。。 然后转移的地方没有特别明白。。。 和之前的找到一个划分的点k不同的是。。。 如果不等于。。 那么 , dp[i][j] = min(dp[i][j],dp[i+1][j]+cost[a[i]]); dp[i][j] = …

light oj 1422 题目链接 题意： 按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来，但是一旦脱下来，这件衣服就报废了。问最少需要几件衣服。 思路：没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这道题是道区间dp的入门题。。。但是不怕被鄙视。。我一点也没思路。。 参考了10多篇题解。。。终于懂了一点。。 参考博客1 参考博客2 参考博客3 参考博客4 **当a[i]和a[j]相等的时候 dp[i][j]=dp[i][j-1] 嗯，就这一个转移。然后就是区间dp的固定写法了。** 这句话让我恍然大悟。。。难道。。都是套路？ dp[i][j]表示的是[i,j]之间最少需要 …

poj 1141题目链接 题意：给出一个括号序列，要求添加最少的括号，使得这个序列变成合法的括号匹配，输出最后的序列。 思路：区间dp。。。有了那么一点思路。。。我们可以用dp[i][j]表示区间[i,j]的序列最少需要添加几个符号使得匹配。。转移的话。。。和之前差不多。。dp[i][j] = dp[i+1][j-1] (s[i]与s[j])匹配。。。不匹配的话也是找中间某个点。。。初始化的话。。要变成最大值。。。比较没思路的是输出括号序列这部分。。。 参考了这篇题解：参考题解 记录路径的思路是。。。记录转移的点。。。 cut[i][j]表示的是区间[i,j]的最优值是由点cut[i][j]这里划分得到的。。。 cut[i][j] …

poj2955题目链接 题意：给出若干括号，问最大匹配数是多少。 思路：没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程？ 完全没思路。。知道了转移方程。。。。嗯，还是不会。。。边界怎么写？状态怎么推？循环顺序? 循环次序？我一点思路都没有。。。。。 人生中第一道区间dp(这话我都说了不知道多少次了。。。每次都学不会。。。。sad) 我的dp水平和其他部分的水平还真是不匹配。。。 看了题解。。。自己写（抄）了一遍。。还是觉得好玄学。。。 细节见代码。 /* *********************************************** Author :111qqz Created Time …

hdu 3980 题目链接 题意：一个有n个石子的环形串，初始没有被涂颜色，两个人轮流，涂连续m个没有被涂色的石子，不能操作的人为负。问先手是否有必赢策略。 思路：和hdu2999很像。。所不同的是。。。那道题是线型的珠子。。。这道题是环型的数字。。。 然而我们机智得发现。。。环形的任意涂一次。。就变成了线型的啊orz。。。 所以先随便取一次，然后剩下的n-m个按照线型串的方法搞，划分区间即可。 由于先随便取了一次，所以和线型的交换输赢的结论。。。 以及。。要特判一次都不能取的情况。。。2A /* *********************************************** Author :111qqz …

hdu2999题目链接 题意：有一串石子，给定一个集合S，每次只能拿连续x个石子，石子必须是在集合S中的数，问先手是否有必赢策略。需要注意石子的位置是不能变化的，也就是说如果一串连续的石子因为中间有石子被取走，那么这段石子就变成不连续的了，也就不能一次取走。 思路：一开始没有读懂题。需要特别强调的是。石子的位置是不能合并的。。 举个例子，如果我有5个石子，S={2},那么我取完一次剩下的情况是 {3,4,5}或者{1},{4,5}或者{1,2},{5}或者{1,2,3} 一共四种。 题意搞清楚以后就好做了。。类似于bomb game那道题。。我们仍然可以把取一次的操作拆分两个子过程，也就是两个区间。我们不关心区间具体的情况，只关心区 …

hdu 2873题目链接 题意：n*m个格子，有若干炸弹。对于在第一行或者第一列的炸弹，爆炸后会到那一行或者那一列的更前面（总的来说就是更靠近左上角）的位置。对于其他位置的炸弹，爆炸后会生成两个炸弹，分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。 思路： 不会做2333 参考了 参考博客1 参考博客2 大概明白了一点。整个游戏可以分为若干个炸弹的游戏的和，而实际上一个不在边界行或者列的炸弹，依然可以继续分，分成两个炸弹的和。而位于(i.j)的炸弹，分成两个炸弹的和，有(i-1)*(j-1)种方案（这个不重要2333） 处于边界行或者列的点的sg值我们是可以知道的。。因为规则单一。。和移动等价。。 然后根据边界来进一 …

hdu2509题目链接 题意：？？？ 思路：同1907 /* *********************************************** Author :111qqz Created Time :2016年07月23日 星期六 04时41分38秒 File Name :code/hdu/2509.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> …

hdu1907题目链接 题意：n堆石子，每次选一堆，最少拿一个，最多拿光那一堆，拿走最有一个的人输。 问是否有必胜策略。 思路：anti-nim问题。。。 要用到sj定理（是啥。。。?) 参考资料：参考博客 SJ定理 **对于任意一个Anti-SG游戏，如果定义所有子游戏的SG值为0时游戏结束，先手必胜的条件： ** **1、游戏的SG值为0且所有子游戏SG值均不超过1。 ** 2、游戏的SG值不为0且至少一个子游戏SG值超过1。 /* *********************************************** Author :111qqz Created Time :2016年07月22日 星期五 23 …