学步园

The 35th ACM/ICPC Asia Regional Hangzhou Site —— Online Contest  1006  Fate Stay Night

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=3646  这里还可以提交

这个题主要就是用DP，不过动态方程算是比较难想的

 // 1006 mnlm 1.0<br /> #include<cstdio><br /> #include<cstdlib><br /> #include<cmath><br /> #include<cstring><br /> #include<vector><br /> #include<algorithm><br /> using namespace std;</p> <p>int k[100001];<br /> int n;<br /> int m;<br /> int K;<br /> int b[10001];<br /> struct DP<br /> {<br /> int ans;<br /> int blood;<br /> bool operator < (const DP &other) const<br /> {<br /> if (ans != other.ans)<br /> {<br /> return ans < other.ans;<br /> }<br /> else<br /> {<br /> return blood > other.blood;<br /> }<br /> }<br /> }dp[101][10001][2];<br /> // dp[a][b][c]中的a表示用过了a次”Command Mantra“，b表示进行到第b个fire bird<br /> // c为1 时表示进行到第b个fire bird的时候用了”Command Mantra“，0则没有用<br /> void Deal(int tt, DP & r)<br /> {<br /> bool flag = true;<br /> while (tt > 0 && r.ans < K)<br /> {<br /> if (tt > r.blood)<br /> {<br /> tt -= r.blood;<br /> r.ans++;<br /> r.blood = k[r.ans];<br /> }<br /> else if (tt == r.blood)<br /> {<br /> tt = 0;<br /> r.ans++;<br /> r.blood = k[r.ans];<br /> }<br /> else<br /> {<br /> if (flag)<br /> {<br /> r.blood -= tt;<br /> }<br /> tt = 0;<br /> }<br /> flag = false;<br /> }<br /> }<br /> int main()<br /> {<br /> while (1)<br /> {<br /> scanf("%d%d%d", &n, &m, &K);<br /> if (!n && !m && !K)<br /> {<br /> break;<br /> }<br /> int i;<br /> for (i = 0; i < n; i++)<br /> {<br /> scanf("%d", &b[i + 1]);<br /> }<br /> for (i = 0; i < K; i++)<br /> {<br /> scanf("%d", &k[i]);<br /> }<br /> int j;<br /> dp[0][0][0].ans = 0;<br /> dp[0][0][0].blood = k[0];<br /> dp[0][0][1].ans = 0;<br /> dp[0][0][1].blood = k[0];<br /> for (i = 1; i <= n; i++)<br /> {<br /> DP & r = dp[0][i][0];<br /> r.ans = dp[0][i - 1][0].ans;<br /> r.blood = dp[0][i - 1][0].blood;<br /> Deal(b[i], r);<br /> dp[0][i][1].ans = 0;<br /> dp[0][i][1].blood = 0x7fffffff;<br /> }<br /> for (i = 1; i <= m; i++)<br /> {<br /> dp[i][0][0].ans = 0;<br /> dp[i][0][0].blood = k[0];<br /> dp[i][0][1].ans = 0;<br /> dp[i][0][1].blood = k[0];<br /> for (j = 1; j <= n; j++)<br /> {<br /> DP & p = dp[i][j - 1][0] < dp[i][j - 1][1] ? dp[i][j - 1][1] : dp[i][j - 1][0];<br /> DP & q = dp[i][j][0];<br /> q.ans = p.ans;<br /> q.blood = p.blood;<br /> Deal(b[j], q);<br /> DP & w = dp[i][j][1];<br /> DP & e = dp[i - 1][j - 1][0] < dp[i - 1][j - 1][1] ? dp[i - 1][j - 1][1] : dp[i - 1][j - 1][0];<br /> w.ans = e.ans;<br /> w.blood = e.blood;<br /> Deal(2 * b[j], w);<br /> }<br /> }<br /> if (dp[m][n][1] < dp[m][n][0])<br /> {<br /> printf("%d/n", dp[m][n][0].ans);<br /> }<br /> else<br /> {<br /> printf("%d/n", dp[m][n][1].ans);<br /> }<br /> }<br /> }<br />