【AHOI2013复仇】BZOJ2165

Posted on 2013-01-01 15:39 Mato_No1 阅读(371) 评论(0)  编辑 收藏 引用 所属分类: BZOJ
原题地址
2013年第一题……纪念一下……

设F[i][j]表示坐i次电梯到达房间j,最多能到几楼,则有
F[i][j]=max{F[i-1][k]+W[k][j]}, 0<=k<n;
这里W[k][j]要注意,如果不存在从k到j的电梯,W[k][j]应设为-INF。
这个方程显然是可以用矩阵乘法来优化的。
然后,问题就是求出最小的i使得F[i]的状态中有值>=M的,这个可以二分(每次看当前解与W的(2^K-1)次方的运算结果,若有解则实际不进行这次运算,否则与W的2^K次方运算)……总时间复杂度是O(n3logM)的,对于本题可能要进行一些常数优化才能过(20个点,每个点5个数据,相当于100个点,时限只有40s),反正本沙茶是卡线过的。

但是,本题有一个细节很重要,必须要说一下(因为本沙茶在这里卡了1h+)……那就是溢出问题……
F[i][j]的值是有可能超过long long的范围的,然而如果硬加高精度的话稳T,这时,在进行矩阵乘法(实际是加法)的时候,需要特判一下,如果这个和超过了INF(INF是~0Ull>>2,>1018),就取INF。这样可能会破坏结合律,但是木有事,因为若两个加数都是非负数,则不会破坏,若有负数,则一定表示无解(-INF),这个特判一下就行了(若两个加数之中有负数,则结果取-INF)。

代码:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 110, MAXLEN = 61;
const ll INF = ~0Ull >> 2;
int n;
ll M, A[MAXLEN][MAXN][MAXN], W0[MAXN][MAXN], _[MAXN][MAXN], res;
void mult(ll A0[][MAXN], ll B0[][MAXN])
{
    re(i, n) re(j, n) _[i][j] 
= -INF; ll __;
    re(i, n) re(j, n) re(k, n) 
if (A0[i][k] >= 0 && B0[k][j] >= 0) {
        __ 
= A0[i][k] + B0[k][j];
        
if (__ > INF) __ = INF;
        
if (__ > _[i][j]) _[i][j] = __;
    }
}
void prepare()
{
    re2(i, 
1, MAXLEN) {
        mult(A[i 
- 1], A[i - 1]);
        re(j, n) re(k, n) A[i][j][k] 
= _[j][k];
        mult(A[i], A[
0]);
        re(j, n) re(k, n) A[i][j][k] 
= _[j][k];
    }
}
void solve()
{
    re(i, n) re(j, n) 
if (i == j) W0[i][j] = 0else W0[i][j] = -INF; bool FF; res = 0;
    rre(i, MAXLEN) {
        FF 
= 0; re(j, n) if (A[i][0][j] >= M) {FF = 1break;}
        
if (FF) continue;
        mult(W0, A[i]);
        FF 
= 0; re(j, n) if (_[0][j] >= M) {FF = 1break;}
        
if (!FF) {
            re(j, n) re(k, n) W0[j][k] 
= _[j][k];
            mult(W0, A[
0]);
            re(j, n) re(k, n) W0[j][k] 
= _[j][k];
            res 
+= 2ll << i;
        }
    }
    FF 
= 0; re(i, n) if (W0[0][i] >= M) {FF = 1break;}
    
if (!FF) res++;
}
int main()
{
    
int tests;
    scanf(
"%d"&tests);
    re(testno, tests) {
        cin 
>> n >> M;
        re(i, n) re(j, n) {scanf(
"%lld"&A[0][i][j]); if (!A[0][i][j]) A[0][i][j] = -INF;}
        prepare();
        solve();
        cout 
<< res << endl;
    }
    
return 0;
}


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理