SRM446 500

 题目连接：http://www.topcoder.com/stat?c=problem_statement&pm=10516&rd=13900

昨天做SRM再次失败，只做出了第一道题。每次做500分都差一点。郁闷的要死，昨天又是死活不过样例，今天醒来想一想，有一个细节方面还没有想清楚就急于去写了。导致算法上有很大的纰漏。

实际上这题算法还是挺容易想的，不过前提是要对矩阵乘法比较了解。实际上这道题也是代表了矩阵乘法的一种类型。我们比较常接触的是那种用乘法和加法的矩阵。实际如下替换之后，矩阵的各种性质也是保持的：

乘法-->加法

加法-->取最大值

这种矩阵，我们的乘法操作是如下的：

 //假设我们是要把Matix A * Matix B的结果存到Matix ans中
 for (i = 0 to n  -1 )
      for (j = 0 to n – 1)
          ans[i,j] = minValue;
          for (k = 0 to n – 1)
                 ans[i][j] = max(ans[i][j], a[i][k] + b[k][j])
从这种操作的意义上来看，就是用来取最长路之类的。跟本题是一样的。

这个题目特殊的地方在于，它有两个要求，一种是必须走K步，中间不可以停下，另一种就是中间可以停。

比赛时我没有看清楚这个条件，以为都是可以停的，所以直接按最原始的做法来做的，等我反应过来看错题的时候，又太急了，没有想清楚就乱去写了，导致算法写反了。

算法如下:

首先我们构造原始矩阵A，A就是由输入的那三个参数来的，但是要加一种情况就是如果两点不可达的时候，要把值设置成无穷小。而不是题目里的0.

然后我们求A = A^stepsPerSecond。这样便可以求出走这些步之后的情况。

再下一步我们不可以直接求A^timeLimit，为什么呢？这是因为我们中间是可以停下的。为了处理这种情况，我们可以把A[1,1]设置为0。这样我们便可以求得最终的答案了。不过这里要注意A[1,1]有可能本来是大于0的，这个时候就不用管它了。不要把这里也设成0。

这种矩阵还有一点和普通的不同在于它的单位矩阵并不是对角线全是1。而是对角线全是0，其它的全是无穷小。这样的矩阵和另一个矩阵相乘之后才可以保持另一个矩阵的不变。

上面如果没有看明白，就直接看下面的代码吧，代码还是比较清楚的：

public class AntOnGraph
{
    static int n;
    public string maximumBonus(string[] p0, string[] p1, string[] p2, int stepsPerSecond, int timeLimit)
    {
        n = p0.Length;
        long[,] st = new long[n, n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int k = (int)(p0[i][j] - '0') * 100 + (int)(p1[i][j] - '0') * 10 + (int)(p2[i][j] - '0');
                k -= 500;
                if (k == -500) {
                    st[i,j] = long.MinValue;
                } else {
                    st[i,j] = k;
                }
            }
        }
        st = mypow(st, stepsPerSecond);
        if (st[1,1] < 0) {
            st[1,1] = 0;
        }
        st = mypow(st, timeLimit);
        if (st[0,1] == long.MinValue) {
            return "IMPOSSIBLE";
        } else {
            return st[0, 1].ToString() ;
        }
    }
    public long[,] mypow(long[,] a, int b)
    {
        long[,]ans = new long[n, n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == j) {
                    ans[i,j] = 0;
                } else {
                    ans[i,j] = long.MinValue;
                }
            }
        }
        for (; b != 0; b >>= 1) {
            if (b % 2 != 0) {
                ans = mul(ans, a);
            }
            a = mul(a, a);
        }
        return ans;
    }
    public long[,] mul(long[,] a, long[,] b) {
        long[,] c = new long[n, n];
        for (long i = 0; i < n; ++i) {
            for (long j = 0; j < n; ++j) {
                c[i,j] = long.MinValue;
                for (int k = 0; k < n; ++k) {
                    if (a[i,k] > long.MinValue && b[k,j] > long.MinValue) {
                        if (a[i,k] + b[k,j] > c[i,j]) {
                            c[i,j] = a[i,k] + b[k,j];
                        }
                    }
                }
            }
        }
        return c;
    }
}