天津外贸网站建设,外包公司前端面试难吗,生成属于自己app的软件,网站页头图片B-打怪(easy)_第二十届同济大学程序设计竞赛#xff08;同步赛#xff09; (nowcoder.com)
问题描述#xff1a;初始攻击是1#xff0c;防御是0#xff0c;血量无穷。怪物防御力永远为0#xff0c;只有初始血量和攻击力。双方每次受到的攻击会掉对手攻击-自己防御的血量…B-打怪(easy)_第二十届同济大学程序设计竞赛同步赛 (nowcoder.com)
问题描述初始攻击是1防御是0血量无穷。怪物防御力永远为0只有初始血量和攻击力。双方每次受到的攻击会掉对手攻击-自己防御的血量。每打死一个怪会掉一个金币可以用一个金币提高自己一攻击力或者一防御力。问在不再受到伤害之前受到的最小伤害是多少。
思路几个月前想的是枚举发现错了。
现在发现这题有重叠子问题和无后效性可以用dp。
每打死一个怪可以提高攻击力或者防御力等价于每次是攻击提高或者防御提高状态表示可以得出。
状态表示F(i,j)表示防御为i攻击为j时受到的最少伤害。
转移方程 F ( i , j ) { i 0 m i n ( F ( i , j ) , F ( i − 1 , j ) r e d u c e ( i − 1 , j ) ) j 1 m i n ( F ( i , j ) , F ( i , j − 1 ) r e d u c e ( i , j − 1 ) ) F(i,j) \begin{cases} i \gt 0 \quad min(F(i,j),F(i-1,j) reduce(i-1,j)) \\ j \gt 1 \quad min(F(i,j), F(i,j-1) reduce(i,j-1)) \end{cases} F(i,j){i0min(F(i,j),F(i−1,j)reduce(i−1,j))j1min(F(i,j),F(i,j−1)reduce(i,j−1)) 其中reduce函数为在攻击为atk防御为df时打死一个怪自己受到的伤害。
int reduce(int df, int atk) {int t m / atk (m % atk 0 ? 0 : 1);t--; // 简单模拟可以知道return t * (n - df);
}边界 F ( i 0 ≤ i ≤ n , j 1 ≤ j ≤ m ) { i 0 且 j 1 1 e l s e i n f F(i_{0 \le i \le n},j_{1 \le j \le m}) \begin{cases} i 0 且j 1 \quad 1 \\ else \quad inf \end{cases} F(i0≤i≤n,j1≤j≤m){i0且j11elseinf 目标 m i n ( F ( n , j 1 ≤ j ≤ m ) , F ( i 0 ≤ i ≤ n , m ) ) min(F(n,j_{1 \le j \le m}), F(i_{0 \le i \le n},m)) min(F(n,j1≤j≤m),F(i0≤i≤n,m))
代码
const int N 2e3 21;
int f[N][N]; // 防御力 i 攻击力 j
void inpfile();
void solve() {int n,m; cinnm; // 攻击血量auto reduce [](int df, int atk) - int {int t m / atk (m % atk 0 ? 0 : 1);t--;return t * (n - df);};memset(f, 0x3f, sizeof(f));f[0][1] 0;rep(i,0,n) {rep(j,1,m) {if(i 0) f[i][j] min(f[i][j], f[i-1][j] reduce(i-1,j));if(j 1) f[i][j] min(f[i][j], f[i][j-1] reduce(i,j-1));}}int ans INF;rep(i,1,m) ans min(ans, f[n][i]);rep(i,0,n) ans min(ans, f[i][m]);coutans;
}
