个人笔记，仅供复习
游戏
【题意描述】
小喵喵喜欢玩RPG游戏。在这款游戏中，玩家有两个属性，攻击和防御，现在小喵喵的攻击和防御都是1，接下来小喵喵会依次遇到n个事件。事件有两种。
1.小喵喵经过修炼，角色升级了，此时可以选择攻击+1或者防御+1.
2.小喵喵遇到了一个敌人，可以选择战斗或者逃跑。如果战斗，胜利后得到a[i]金钱。如果逃跑，则无事发生，但是以后也不能再回来打这个怪物了。
对于一场战斗来说，如果小喵喵的攻击力大于等于atk[i]，防御力大于等于def[i]，那么他可以无伤打败这只怪物，从而他选择打怪，否则他发现自己会受伤，从而选择逃跑。
现在小喵喵想知道，通过巧妙地选择升级时加的属性，他最多能够从这n个事件中获得多少金钱。
【输入格式】
第1行一个整数n。
第2~n+1行每行会有一个字符’U’或’M’，分别表示升级和怪物，如果是怪物，之后有空格隔开的三个整数a[i],atk[i],def[i]。
【输出格式】
一个整数，表示最多的金钱。
【样例输入输出】
5
U
U
M 2 1 2
M 5 2 1
M 3 1 3 7
【样例解释】
小喵喵可以选择分别增加一次攻击和防御，从而可以打3号和4号怪物。总的金钱是2+5=7.
【数据范围】
对于20%的数据，n<=10
对于另外20%的数据，所有怪物的def[i]为1.
对于另外30%的数据，n<=100
对于所有的数据，n<=2000,1<=atk[i],def[i]<=n,a[i]<=109.
解题思路：第一次看到这题我想到的是用图的方法（最近学图论入迷了）。但事实上这题是典型的用动态规划解题。看了老师给的代码才茅塞顿开。
解题代码：老师给的答案，自己按照理解写的注释。
#include <iostream>
using namespace std;
long long dp[2000][2000], maxN;
int main() {
ios::sync_with_stdio(false);
int n, utimes = 2, a, atk, def;
char c;
cin >> n;
while (n--) {
cin >> c;
if (c == 'U') {
++utimes;
for (int i = 1; i < utimes; ++i)
//此处将i看作攻击，若升级i点攻击，则升级utimes-i防御
dp[i][utimes-i] = max(dp[i-1][utimes-i], dp[i][utimes-i-1]);
//是少升一点攻击好呢，还是少升一点防御好呢
}else {
cin >> a >> atk >> def;
for (int i = atk; i < utimes; ++i)
if (utimes-i >= def) dp[i][utimes-i] += a, maxN = max(maxN, dp[i][utimes-i]);
//当前最多获得多少钱
}
}
cout << maxN << endl;
return 0;
}