Posts

1874: [BeiJing2009 WinterCamp]取石子游戏 # Time Limit: 5 Sec Memory Limit: 162 MB Submit: 726 Solved: 296 [Submit][Status][Discuss] Description # 小H和小Z正在玩一个取石子游戏。 取石子游戏的规则是这样的，每个人每次可以从一堆石子中取出若干个石子，每次取石子的个数有限制，谁不能取石子时就会输掉游戏。 小H先进行操作，他想问你他是否有必胜策略，如果有，第一步如何取石子。

cf429 b 题目链接 题意： n*m个格子，每个格子有一个人value a[i][j]>0，连个人，一个从左上角到右下角，每次只能向下或者向右移动，一个从左下到右上，每次只能向上或者向右移动，现在要求两个人恰好相遇一次，相遇点的a不算数，问在满足这样的条件下使得两个人的a最大。。。（很坑的一点是。。这里相遇并不考虑时间。。就是说，不在同一时间都到达过某一格子，也认为相遇。所以我认为，题目含义更准确的说法是，路径只有一个交点）

hdu 2050题目链接 题意：n条折线。。最多能把平面分成几部分。。 思路：联想到m条直线，最多能把平面分成m*(m+1)/2+1部分。。 画图发现。。。 f[2*n-1]==g[n]。。

hdu 2049 题目链接 题意：n个妹子和n个汉子对应。。然后让每个汉子取选一个妹子，不能重复，问恰好有m个汉子选错妹子的可能的方案数。 思路：从n个中选n-m个，然后做剩余m个错排即可。

。。。重新编译一次就可以了。。。orz

hdu2048 题目链接 题意：n个人不放回的从一个有n个每个人对应id的卡片的盒子取一张卡片，取的正好和自己的对应就算中奖。求所有人都没有中奖的概率。 思路：错排。。。 复习了一下错排公式。。。d[n] = (n-1)*(d[n-1]+d[n-2]) （d[1]=0,d[2]=1）

hdu 2047 题目链接 题意：一个由’E’ ‘O’ ‘F’ 组成的长度为n的字符串。‘O’不能相邻。。问方案数。。 思路：递推。。。蒙对了（误 考虑第n位，如果为’E’或者‘F’，此时对n-1位没有限制，答案为f[n-1]，所以 一共是2×f[n-1]

hdu2045 题目链接 题意： 一串 方格，每个格子可以涂三种颜色，要求相邻的格子颜色不能相同，首尾格子也不能相同。 思路：递推。没推出来23333 我好菜啊.jpg. 考虑有n个格子。。那么假设第n-1个格子的颜色是a，根据第一个格子和第n-1个格子颜色是否相同分为两种情况。

hdu2018题目链接 题意：第1年有1头奶牛，每年生一头奶牛，新生的奶牛从生下来的第四年（包括生下来那年）也开始每年一头奶牛。 问第n年有多少头奶牛。 思路：最容易想到的。。递推一下。。。dp[i] = dp[i-1] + dp[i-3] (注意初始化不是一个dp[1]=1，而是dp[1..4]=1..4)

hdu2084题目链接 题意：dp入门题。。。数字三角形。。 思路： 昨天看mit公开课。。。讲到dp的精髓是sub-problem+ reuse… 为什么自底向上呢。。。 初始化dp[n][i] = a[n][i]其实是在处理只有最后一行的子问题。。。

hdu 4283题目链接 题意：有N个人按顺序排成一排上台表演，每个都有一个num[]值，若在他是第k个上场的人，则会有num[]*(k-1)的unhappiness。台下有一个黑屋（stack），对每一个人，可以选择让他先进屋子或者直接上台。现在让你找到一个最优方案使得所有人的unhappiness之和最小。

poj 3661题目链接 题意：锻炼，一共n分钟，每分钟可以选择跑步或者休息，第i分钟跑步可以跑d[i]米，并增加一点疲劳度，如果选择休息，那么每分钟减少1点疲劳值。一旦开始休息，必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0，否则之后会感觉身体被掏空。问n分钟最远多多远。

poj 1651题目链接 题意：n个数，删掉a[i]的得分是a[i]*a[i-1]*a[i+1]，两个端点的不允许删。问删完n-2个数得到的最小分数是多少。 思路：能想到设计状态dp[i][j]表示区间[i,j]的最小分数。然后就没思路了。 T T

poj 3280 题目链接 题意：一个字符串，给出添加一个字符或者删掉该字符的花费，问最小的话费使得字符串变成回文串。 思路：dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。

light oj 1422 题目链接 题意： 按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来，但是一旦脱下来，这件衣服就报废了。问最少需要几件衣服。 思路：没有思路。我连这题是dp都看不出来。。知道是dp也一点思路都没。。虽然这道题是道区间dp的入门题。。。但是不怕被鄙视。。我一点也没思路。。

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

poj2955题目链接 题意：给出若干括号，问最大匹配数是多少。 思路：没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程？ 完全没思路。。知道了转移方程。。。。嗯，还是不会。。。边界怎么写？状态怎么推？循环顺序？ 循环次序？我一点思路都没有。。。。。

hdu 3980 题目链接 题意：一个有n个石子的环形串，初始没有被涂颜色，两个人轮流，涂连续m个没有被涂色的石子，不能操作的人为负。问先手是否有必赢策略。 思路：和hdu2999很像。。所不同的是。。。那道题是线型的珠子。。。这道题是环型的数字。。。

hdu2999题目链接 题意：有一串石子，给定一个集合S，每次只能拿连续x个石子，石子必须是在集合S中的数，问先手是否有必赢策略。需要注意石子的位置是不能变化的，也就是说如果一串连续的石子因为中间有石子被取走，那么这段石子就变成不连续的了，也就不能一次取走。

hdu 2873题目链接 题意：n*m个格子，有若干炸弹。对于在第一行或者第一列的炸弹，爆炸后会到那一行或者那一列的更前面（总的来说就是更靠近左上角）的位置。对于其他位置的炸弹，爆炸后会生成两个炸弹，分别到那一行的更前面或者那 一列的更前面。问先手是否有必赢策略。