题目

Description

招商银行遇到一位很奇怪的顾客。这位顾客起初用一些人民兑换了另一种货币，然后不断地用一种货币兑换另一种货币，最后又换回人民币。令人惊奇的是，最后换回的人民币居然比他最初带来的多了一些。
例如这样一个兑换过程：
假设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后，最多能让我们持有的货币增加多少单位？

Input

输入包含多组数据。 每组数据第一行包含两个整数：n (1≤n≤100), k (0≤k≤100)，第二行为一个实数m (0ij单位的货币j，注意，不一定能反向兑换。若aij=0，则表示不能直接用货币i兑换货币j。显然不能用货币i换货币i，这样没有意义。 输入以n=k=0结束。

Output

对每组数据输出我们持有的货币1最多能增值多少，精确到小数点后两位。如果不可能增值，则输出”0.00”

Sample Input

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

Sample Output

0.01
0.00

题解

与其说是动态规划,不如说这道题是 贪心+模拟
用计算器跟着样例走一遍就能明白题意

dp[i][j] 表示兑换 j 次且此时为货币 i 的最大钱数
因此初始时为 dp[1][0]
最后结果为 dp[1][k]

每次状态转移为 dp[i][j] = max{ dp[t][j] } (1<=t<=n)
根据转移方程应该先遍历 j 再遍历 i

时间复杂度为 O(n³)

最后要注意如果不能赚钱要输出 0.00

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
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("%d%d",&n,&k);
    if(n == 0 && k == 0)
        return false;
    scanf("%lf",&dp[1][0]);

    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            scanf("%lf",&hl[i][j]);


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

        }

    if(dp[1][k] - dp[1][0] < 0.0)
        printf("0.00\n");
    else
        printf("%.2f\n",dp[1][k] - dp[1][0]);

    return true;
}

int main() {
    while(Do());
    return 0;
}