<h1 id="heading">题目</h1>
<blockquote>
<h2 id="description">Description</h2>
<blockquote>
招商银行遇到一位很奇怪的顾客。这位顾客起初用一些人民兑换了另一种货币，然后不断地用一种货币兑换另一种货币，最后又换回人民币。令人惊奇的是，最后换回的人民币居然比他最初带来的多了一些。 
例如这样一个兑换过程： 
假设1单位人民币兑换6.89单位火星币，1单位火星币兑换0.18单位水星币，1单位水星币兑换0.81单位人民币。 
我们用1.20单位人民兑换得8.27单位火星币，然后用这8.27单位火星币兑换得1.49单位水星币，最后用1.49单位水星币兑换到1.21单位人民币。 
奇迹就这样发生了。聪明的你一定已经发现了，这都是四舍五入的功劳。 
当然这种事情在现实中是不可能的，但我们还是来研究一下这个问题。 
假设共有n种货币，编号从1到n。我们最初持有m单位的货币1。已知各种货币之间兑换比率，每次兑换后都四舍五入到小数点后两位。请问兑换k次且换回到货币1后，最多能让我们持有的货币增加多少单位？
 
</blockquote>
<h2 id="input">Input</h2>
<blockquote>
输入包含多组数据。 每组数据第一行包含两个整数：n (1≤n≤100), k (0≤k≤100)，第二行为一个实数m (0ij单位的货币j，注意，不一定能反向兑换。若aij=0，则表示不能直接用货币i兑换货币j。显然不能用货币i换货币i，这样没有意义。 输入以n=k=0结束。
</blockquote>
<h2 id="output">Output</h2>
<blockquote>
对每组数据输出我们持有的货币1最多能增值多少，精确到小数点后两位。如果不可能增值，则输出”0.00”
</blockquote>
<h2 id="sample-input">Sample Input</h2>
<blockquote>
3 3 
1.20 
0.00 6.89 0.00 
0.00 0.00 0.18 
0.81 0.00 0.00 
1 0 
1.00 
0.00 
0 0
</blockquote>
<h2 id="sample-output">Sample Output</h2>
<blockquote>
0.01 
0.00
</blockquote>
</blockquote>
<h1 id="heading-1">题解</h1>
与其说是动态规划,不如说这道题是 贪心+模拟 
用计算器跟着样例走一遍就能明白题意
<code>dp[i][j]</code> 表示兑换 <code>j</code> 次且此时为货币 <code>i</code> 的最大钱数 
因此初始时为 <code>dp[1][0]</code> 
最后结果为 <code>dp[1][k]</code>
每次状态转移为 <code>dp[i][j] = max{ dp[t][j] } (1&lt;=t&lt;=n)</code> 
根据转移方程应该先遍历 <code>j</code> 再遍历 <code>i</code>
时间复杂度为 O(n3)
最后要注意如果不能赚钱要输出 <code>0.00</code>
<h1 id="heading-2">代码</h1>
<pre style="background-color:#fff">/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include &lt;cstdio&gt;
#include &lt;algorithm&gt;
#include &lt;cstring&gt;
#include &lt;cmath&gt;
#include &lt;string&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
#include &lt;queue&gt;
#include &lt;stack&gt;
#include &lt;map&gt;
#include &lt;set&gt;
#include &lt;functional&gt;
using namespace std;

const int maxn = 105;
const int maxk = 105;

double hl[maxn][maxn];
double dp[maxn][maxk];

inline double standard(double a) {
 return (double)((int)(a * 100 + 0.5)) / 100;
}

bool Do() {
 int n,k;
 scanf(&#34;%d%d&#34;,&amp;n,&amp;k);
 if(n == 0 &amp;&amp; k == 0)
 return false;
 scanf(&#34;%lf&#34;,&amp;dp[1][0]);

 for(int i = 1;i &lt;= n;i++)
 for(int j = 1;j &lt;= n;j++)
 scanf(&#34;%lf&#34;,&amp;hl[i][j]);


 for(int j = 1;j &lt;= k;j++)
 for(int i = 1;i &lt;= n;i++) {
 dp[i][j] = 0;
 for(int t = 1;t &lt;= n;t++) {
 dp[i][j] = max(standard(dp[t][j - 1] * hl[t][i]),dp[i][j]);
 }

 }

 if(dp[1][k] - dp[1][0] &lt; 0.0)
 printf(&#34;0.00\n&#34;);
 else
 printf(&#34;%.2f\n&#34;,dp[1][k] - dp[1][0]);

 return true;
}

int main() {
 while(Do());
 return 0;
}
</pre>

AOJ 261.货币兑换