88 条题解

  • 2
    @ 2017-03-18 14:42:25

    高精度的题目为什么不用python?(说实在的,这是我第一次用python做dp)

    n,m=[int(i) for i in raw_input().split()]
    ans=0
    while n>0:
        n-=1
        f=[[0]*(m-i) for i in range(m)] #从j往后选i个数的最优解
        f[0]=[int(i) for i in raw_input().split()]
        for i in range(1,m):
            for j in range(m-i):
                if i==1:
                    f[i][j]=2*max(f[0][j]*2+f[0][j+1],f[0][j+1]*2+f[0][j])
                else:
                    f[i][j]=f[i-1][j+1]+f[0][j]
                    f[i][j]=2*max(f[i][j],f[i-1][j]+f[0][i+j])
        ans+=f[m-1][0]
    print(ans)
    
  • 2
    @ 2016-01-09 15:52:00

    依题意得,行与行之间毫无关联,因此各行之间相互独立,完全可以一行一行地处理。每一行都选出一个最大值,加起来就是答案了。对于第 i 行,每次都只能从两边取,所以一个状态只可能由两个状态转移而来:左边或右边。令**f[l][r]代表从左起边取了l个,右边起取了r个数的最高分值。**用目前是第几次取来划分阶段。
    方程很好想: f[l][r] = Max{ f[l-1][r] + matrix[i][l-1] · 2^j, f[l][r-1] + matrix[i][m-r] · 2^j }
    其中 matrix 存储矩阵,i 表示目前正在处理第几行,所以 matrix[ i ][ 0 .. m-1] 存储的是该行的数字。j 表示目前是第几次取。写成代码如下:

    for(i=0; i<row; i++){
    memset(f, 0, sizeof(f));
    for(j=1; j<=column; j++){ //columns taken
    for(l=0; l<=j; l++){ //columns taken from left side
    r = j-l; //columns taken from right side
    if(l > 0)
    f[l][r] = f[l-1][r] + matrix[i][l-1]*pow(2, j);
    if(r > 0)
    f[l][r] = MAX(f[l][r], f[l][r-1] + matrix[i][column-r]*pow(2, j));
    }
    }
    j = 0;
    for(l=0; l<=column; l++)
    j = MAX(j, f[l][column-l]);
    sum += j;
    }

    由于数据范围很大,所以需要高精度,还要预处理一下 2 的幂。写了一百多行就不贴上来了。本以为常数很大,但加起来不到 600ms 就 AC 了。注意第一组测试数据,貌似答案是0,结果我忘记考虑这一点,没有输出,还WA了一次。

  • 1
    @ 2019-07-22 19:18:36

    大整数模板我就不贴出来了,这里给一个之前没有加大整数的题解便于理解,该题解60分。
    首先,对整个矩阵取数,由于行与行之间取数的独立性。我们可以理解为对矩阵的每一行都取一遍。
    接下来看一行怎么取,记dp(i,j)为i到j之间的数字都没取过,从两端向中间dp。初始化dp(0,m-1)=0.

    dp[k][r]=max(dp[k-1][r]+ma[i][k-1]*base,dp[k][r+1]+ma[i][r+1]*base);
    

    题解:

    #include <iostream>
    #include <cstring>
    #define ULL unsigned long long
    
    using namespace std;
    
    int n,m;
    int ma[80][80];
    ULL dp[80][80];
    
    int main()
    {
        cin>>n>>m;
        int i,j,k,r;
        ULL ans=0,base,hax;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                cin>>ma[i][j];
            }
        }
        for(i=0;i<n;i++)
        {
            memset(dp,0,sizeof(dp));
            base=2;
            hax=0;
            for(j=1;j<m;j++,base*=2)
            {
                for(k=0;k<=j;k++)
                {
                    r=m-1-j+k;
                    if(k==0)
                    {
                        dp[k][r]=dp[k][r+1]+ma[i][r+1]*base;
                    }
                    else if(k==j)
                    {
                        dp[k][r]=dp[k-1][r]+ma[i][k-1]*base;
                    }
                    else
                    {
                        dp[k][r]=max(dp[k-1][r]+ma[i][k-1]*base,dp[k][r+1]+ma[i][r+1]*base);
                    }
                }
            }
            for(j=0;j<m;j++)
            {
                hax=max(hax,dp[j][j]+ma[i][j]*base);
            }
            ans+=hax;
        }
        cout<<ans<<endl;
        return 0;
    }
    
  • 1
    @ 2016-10-24 15:58:15

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 3480 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 3484 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 3480 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 3484 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 3484 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 3480 KiB, score = 10
    测试数据 #6: Accepted, time = 93 ms, mem = 3484 KiB, score = 10
    测试数据 #7: Accepted, time = 296 ms, mem = 3484 KiB, score = 10
    测试数据 #8: Accepted, time = 375 ms, mem = 3484 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 3480 KiB, score = 10
    Accepted, time = 870 ms, mem = 3484 KiB, score = 100
    思想下面有大犇给了,感觉自己代码*好长、好慢*啊~~

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    inline int read() {
        int t = 1,x = 0;
        char ch = getchar();
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) t = -1;
            ch = getchar();
        }
        while ( ch >= '0' && ch <= '9' ) {
            x = x * 10 + ch - '0';
            ch = getchar();
        }
        return t * x;
    }
    struct node {
        int len,s[111];
        node() {len=1;memset(s,0,sizeof s);}
        node operator=(const char* num) {
            len = strlen(num);
            for (int i=0;i<len;i++) s[i] = num[len-i-1]-'0';
            return *this;
        }
        node operator=(const int num) {
            char a[101];
            sprintf(a,"%d",num);
            *this = a;
            return *this;
        }
        node(int num) {*this = num;};
        node operator+(const node & a) {
            node c;
            c.len = max(a.len,len)+1;
            for (int i=0,x=0;i<c.len;i++) {
                c.s[i] = s[i] + a.s[i] + x;
                x = c.s[i]/10;
                c.s[i] = c.s[i]%10;
            }
            while ( c.s[c.len-1] == 0 && c.len > 1 ) --c.len;
            return c;
        }
        node operator+=(const node & a) {
            *this = *this + a;
            return *this;
        }
        node operator*(const node & x) {
            node c;
            c.len = len + x.len;
            for (int i=0;i<len;i++) {
                for (int j=0;j<x.len;j++) {
                    c.s[i+j] += s[i]*x.s[j];
                    c.s[i+j+1] += c.s[i+j]/10;
                    c.s[i+j]%=10;
                }
            }
            while (c.s[c.len-1] == 0 && c.len > 1) --c.len;
            return c;
        }
        bool operator < (const node & x) const {
            if ( len != x.len) return len<x.len;
            for (int i=len-1;i>=0;i--) {
                if ( s[i] != x.s[i] ) return s[i]<x.s[i];
            }
            return 0;
        }
    };
    node Max(node a,node b) {
        if ( a < b ) return b;
        else return a;
    }
    node che(int j) {
        node x = (int)1,y = 2;
        for (int i=1;i<=j;i++)
            x = x * y;
        return x;
    }
    void print(node a) {
        for (int i=a.len-1;i>=0;i--)
            cout<<a.s[i];
        cout<<endl;
    }
    node dp[81][81],ans;
    int n,m,map[81][81];
    int main() {
        freopen("game.in","r",stdin);
        freopen("game.out","w",stdout);
        n = read(); m = read();
        for (int i=1;i<=n;i++) 
            for (int j=1;j<=m;j++)
                map[i][j] = read();
        for (int i=1;i<=n;i++) {
            node maxx;
            dp[0][0] = 0;
            dp[0][1] = (map[i][m] * 2);
            dp[1][0] = (map[i][1] * 2);
            for (int j=1;j<=m;j++) {
                node p = che(j);
                maxx = (int)0;
                for (int k=0;k<=j;k++) {
                    node a = map[i][k],b = map[i][m-j+k+1];
                    a = a * p;
                    b = b * p;
                    if ( k > 0 ) a = a + dp[k-1][j-k];
                    if ( k < j ) b = b + dp[k][j-k-1];
                    dp[k][j-k] = Max(a,b);
                    if ( j == m ) maxx = Max(dp[k][j-k],maxx);
                }
            }
            ans += maxx;
        }   
        print(ans);
        return 0;
    }
    
  • 0
    @ 2019-06-20 12:53:02

    如果使用GCC内置变量__uint128_t也是可以满足要求的,不用再写高精度类了

    话说JAVA的BigInteger和Python真的是让人羡慕。

  • 0
    @ 2017-09-08 10:33:49

    前面已经有个题解说得很好了。
    我就贴个代码吧,主要还是考高精度,从2^80就可以看出long是存不下的。

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct BIGINT {
        int len, num[35];   
        void CLEAR () {
            len=1;
            memset(num, 0, sizeof(num));    
        }
        void PRINT () {
            //printf("%d\n", len);
            for(int i=len; i>=1; i--) printf("%d", num[i]);     
        }
        BIGINT () {
            CLEAR();
        }
        BIGINT (int x) {
            CLEAR();    
            while(x) {
                num[len]=x%10;
                x/=10;
                len++;  
            }
            len--;
        }
        BIGINT operator + (BIGINT x) {
            BIGINT a;
            int maxlen=max(len, x.len);
            for(int i=1; i<=maxlen;i++) a.num[i]=num[i]+x.num[i];
            while(a.num[a.len]>=10||a.len<maxlen) {
                a.num[a.len+1]+=a.num[a.len]/10;
                a.num[a.len++]%=10;
            }    
            return a;
        }
        BIGINT operator * (BIGINT x) {
            BIGINT a;
            int maxlen=len+x.len-1;
            for(int i=1; i<=len; i++) 
                for(int j=1; j<=x.len; j++)
                    a.num[i+j-1]+=num[i]*x.num[j];
            while(a.num[a.len]>=10||a.len<maxlen) {
                a.num[a.len+1]+=a.num[a.len]/10;
                a.num[a.len++]%=10;
            }    
            return a;
        }
        bool operator == (BIGINT x) {
            if (len!=x.len) return 0;
            for(int i=1; i<=len; i++) 
                if (num[i]!=x.num[i]) return 0;
            return 1;    
        }
        bool operator > (BIGINT x) {
            if (len<x.len) return 0;
            else if (len>x.len) return 1;
            for(int i=len; i>=1; i--) 
                if (num[i]>x.num[i]) return 1;
                else  if (num[i]<x.num[i]) return 0;
            return 0;   
        }
    };
    int N, M;
    int A[85][85];
    BIGINT P[85], F[85][85][85];
    void POW2 () {
        
        P[0]=1;
        for(int i=1; i<=80; i++) P[i]=P[i-1]*2; 
        
    }
    int main () {
        
        POW2(); 
        scanf("%d%d", &N, &M);
        for(int i=1; i<=N; i++)
            for(int j=1; j<=M; j++)
                scanf("%d", &A[i][j]);
        BIGINT a=0, b=0, c=0, d=0, ans=0;
        for(int f=1; f<=N; f++) { 
            for(int i=2; i<=M; i++) 
                for(int l=1; l+(M-i)<=M; l++) {  
                    int r=l+(M-i); 
                    a=F[f][l-1][r]+P[i-1]*A[f][l-1];
                    b=F[f][l][r+1]+P[i-1]*A[f][r+1];
                    if (a>b) F[f][l][r]=a;
                    else F[f][l][r]=b;              
                }   
            c.CLEAR();   
            for(int i=1; i<=M ; i++) {  
                d=F[f][i][i]+P[M]*A[f][i];  
                if (d>c) c=d;
            }
            ans=ans+c;    
        }
        ans.PRINT();
        return 0;
        
    }
    
  • 0
    @ 2016-11-15 23:26:17

    果然还是要写高精度的么。。。
    可怕死了

  • 0
    @ 2016-09-21 20:28:50

    type
    bigint=array [0..100] of longint;
    var
    a:array [1..100,1..100] of longint;
    f:array [1..100,1..100] of bigint;
    i,j,m,n,k:longint;
    t,s,ans:bigint;

    procedure add(var x,y:bigint);
    var i,c:longint;
    begin
    for i:=x[0]+1 to y[0] do x[i]:=0;
    for i:=1 to y[0] do x[i]:=x[i]+y[i];
    if x[0]<y[0] then x[0]:=y[0];
    x[x[0]+1]:=0;
    c:=0;
    for i:=1 to x[0] do
    begin
    c:=x[i] div 10;
    x[i+1]:=x[i+1]+c;
    x[i]:=x[i] mod 10;
    end;
    if c>0 then x[0]:=x[0]+1;
    end;

    procedure max(var x,y,z:bigint);
    var
    i:longint;
    begin
    if y[0] > z[0] then begin
    x := y;
    exit;
    end
    else if y[0] < z[0] then begin
    x := z;
    exit;
    end
    else begin
    for i:=y[0] downto 1 do begin
    if y[i]<z[i] then
    begin
    x:=z;
    exit;
    end;
    if y[i]>z[i] then
    begin
    x:=y;
    exit;
    end;
    end;
    x:=y;
    end;
    end;

    procedure print(var x:bigint);
    var
    i:longint;
    begin
    for i:=x[0] downto 1 do write(x[i]);
    if x[0] = 0 then write(0);
    writeln;
    end;

    procedure load (var x:bigint;a:longint);
    begin
    x[0]:=0;
    while a>0 do
    begin
    x[0]:=x[0]+1;
    x[x[0]]:=a mod 10;
    a:=a div 10;
    end;
    end;

    begin
    readln(n,m);
    for k:=1 to n do begin
    for j:=1 to m do

    read(a[k,j]);

    for i:=1 to m do
    load(f[i,i],a[k,i]);
    for i:=m downto 1 do
    for j:=i+1 to m do begin

    load(t,a[k,i]);
    add(t,f[i+1,j]);
    add(t,f[i+1,j]);

    load(s,a[k,j]);
    add(s,f[i,j-1]);
    add(s,f[i,j-1]);

    max(f[i,j],s,t);
    end;
    add(ans,f[1,m]);
    end;
    add(ans,ans);
    print(ans);
    end.

  • 0
    @ 2016-07-22 11:34:09
    c++
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    const int maxn = 80 + 5;
    
    struct bignum{
        int l; short int w[1000];
        bignum(){
            l = 1; memset(w, 0 , sizeof(w));
        }
        
        bignum(int x){
            l = 0; memset(w, 0 , sizeof(w));
            while(x){
                w[l] = x % 10; x /= 10;
                l++;
            }
        }
        
        bool operator > (bignum x){
            if(l > x.l) return true;
            else 
            if(l == x.l) 
                for(int i = l - 1; i >= 0; i--){
                    if(w[i] > x.w[i]) return true;
                    if(w[i] < x.w[i]) return false;
                }
            
            return false;
        }
        
        bignum operator + (const bignum& x){
            bignum ans;
            if(l>x.l) ans.l=l;
            else ans.l=x.l;
            
            for(int i = 0; i < ans.l; i++){
                ans.w[i] += w[i] + x.w[i];
                ans.w[i+1] += ans.w[i] / 10;
                ans.w[i] %= 10;
            }
            if(ans.w[ans.l]) ans.l++;
            return ans;
            
        }
        
        bignum operator * (const bignum& x){
            bignum ans;
            ans.l = l + x.l;
            for(int i=0;i<l;i++){
                for(int j=0;j<x.l;j++){
                    ans.w[i+j] += w[i] * x.w[j];
                    ans.w[i+j+1] += ans.w[i+j] / 10;
                    ans.w[i+j] %= 10;
                }
            }
            if(ans.w[ans.l-1]==0) ans.l--;
            return ans;
        }
        bignum operator * (int x){
            bignum ans(x);
            return operator*(ans);
        }
        
        void print(){
            if(l == 0) cout<<0;
            for(int i = l - 1; i >= 0; i--)
                printf("%d", w[i]);
            printf("\n");
        }
        
        
    };
    int a[maxn]={0};
    bignum d[maxn][maxn];//d[i][j]:某一排!!从i到j能够取到的最大值 
    int n, m;
    int main(){
        cin >> n >> m;
        bignum ans = 0; int x;
        
        bignum mi[83];//m[i]为2的i次幂
        mi[0] = 1;
        for(int i = 1; i <= m; i++){
            mi[i] = mi[i-1];
            mi[i] = mi[i] * 2;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                cin >> x; a[j] = x;
            }
            for(int i = 1; i <= m; i++) d[i][i] = mi[m]*a[i];
            for(int l = 1; l < m; l++){
                for(int i = 1; i < m; i++){
                    if(i + l > m) break;
                    bignum v1 = mi[m - l] * a[i]   + d[i+1][i+l];
                    bignum v2 = mi[m - l] *a[i+l] + d[i][i+l-1];
                    if(v1>v2) d[i][i+l] = v1;
                    else d[i][i+l] = v2;
                }
            }
            ans = ans + d[1][m];
        }
        
        ans.print();
        
        return 0;
    
    }
    
  • 0
    @ 2016-07-17 21:05:17

    type tt=record
    k:longint;
    t:array [0..105] of longint;
    end;
    var
    a:array [0..100] of tt;
    f:array [0..100,0..100] of tt;
    n,m,i,j,q,u:longint;
    x,y,p:tt;
    procedure cheng(x:longint; a:tt; var b:tt);
    var i:longint;
    begin
    fillchar(b.t,sizeof(b.t),0);
    for i:=1 to a.k do b.t[i]:=a.t[i]*x;
    for i:=1 to a.k do begin
    inc(b.t[i+1],b.t[i] div 10);
    b.t[i]:=b.t[i] mod 10;
    end;
    b.k:=a.k;
    if (b.t[b.k+1]<>0) then inc(b.k);
    end;
    procedure jia(a,b:tt; var c:tt);
    var i:longint;
    begin
    if (a.k>b.k) then c.k:=a.k else c.k:=b.k;
    fillchar(c.t,sizeof(c.t),0);
    for i:=1 to c.k do c.t[i]:=b.t[i]+a.t[i];
    for i:=1 to c.k do begin
    inc(c.t[i+1],c.t[i] div 10);
    c.t[i]:=c.t[i] mod 10;
    end;
    if (c.t[c.k+1]>0) then inc(c.k);
    end;
    procedure make(var a:tt; p:longint);
    begin
    fillchar(a.t,sizeof(a.t),0);
    a.k:=0;
    if (p=0) then begin a.k:=1; a.t[1]:=0; exit; end;
    while (p<>0) do begin inc(a.k); a.t[a.k]:=p mod 10; p:=p div 10; end;
    end;
    procedure print(a:tt);
    var i:longint;
    begin
    for i:=a.k downto 1 do write(a.t[i]);
    writeln;
    end;
    function bj(a,b:tt):boolean;
    var i:longint;
    begin
    if (a.k<b.k) then exit(false);
    if (a.k>b.k) then exit(true);
    for i:=a.k downto 1 do begin
    if (a.t[i]<b.t[i]) then exit(false);
    if (a.t[i]>b.t[i]) then exit(true);
    end;
    exit(false);
    end;
    begin
    read(n,m);
    for q:=1 to n do
    begin
    for i:=1 to m do begin read(u); make(a[i],u); end;
    for i:=1 to m do cheng(2,a[i],a[i]);
    for i:=1 to m do
    for j:=1 to m do begin
    fillchar(f[i,j].t,sizeof(f[i,j].t),0);
    f[i,j].k:=0; end;
    for i:=1 to m do f[i,i]:=a[i];
    for i:=2 to m do
    for j:=1 to m-i+1 do
    begin
    cheng(2,f[j,j+i-2],x); jia(x,a[j+i-1],x);
    cheng(2,f[j+1,j+i-1],y); jia(y,a[j],y);
    if bj(x,y) then f[j,j+i-1]:=x else f[j,j+i-1]:=y;
    end;
    jia(p,f[1,m],p);
    end;
    print(p);
    end.

  • 0
    @ 2016-07-12 17:38:23

    #include <cstdio>
    #include <iostream>
    #include <cstring>

    using std::max;

    int plusx(int a[],int b[],int c[]){
    memset(c,0,sizeof(int)*25);
    int len=a[0]>b[0]?a[0]:b[0];
    for(int i=1;i<=len;i++){
    c[i]+=a[i]+b[i];
    c[i+1]+=c[i]/10000;
    c[i]%=10000;
    }
    len++;
    while(c[len]==0&&len>1)
    len--;
    c[0]=len;
    }

    void plus(int a[],int x){
    int len,k;
    len=a[1]+x;
    k=len/10000;
    a[1]=len%10000;
    for(int i=2;i<=a[0]||k;i++){
    len=a[i]+k;
    k=len/10000;
    a[i]=len%10000;
    }
    len=a[0]+1;
    while(a[len]==0&&len>1)len--;
    a[0]=len;
    }

    //大于为1 小于或等于为0
    int bigger(int a[],int b[]){
    if(a[0]!=b[0])
    return a[0]>b[0];
    int flag;
    for(int i=a[0];i>=1;i--)
    if(a[i]!=b[i]){
    flag=a[i]>b[i];
    break;
    }
    return flag;
    }

    void output(int a[]){
    printf("%d",a[a[0]]);
    for(int i=a[0]-1;i>=1;i--)
    printf("%04d",a[i]);
    }

    int main(){
    // freopen("game.in","r",stdin);
    int n,m;
    int a[100][100];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&a[i][j]);
    int sum[30]={0};
    sum[0]=1;
    int f[100][100][30];
    for(int k=1;k<=n;k++){
    memset(f,0,sizeof(f));
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++)
    f[i][j][0]=1;
    for(int i=1;i<=m;i++){
    f[i][1][1]=2*a[k][i];
    }
    for(int j=2;j<=m;j++)
    for(int i=1;i<=m-j+1;i++){
    int p1[30]={1},p2[30]={1};
    memcpy(p1,f[i+1][j-1],sizeof(p1));
    plus(p1,a[k][i]);
    memcpy(p2,f[i][j-1],sizeof(p2));
    plus(p2,a[k][i+j-1]);
    if(bigger(p1,p2))
    memcpy(f[i][j],p1,sizeof(p1));
    else
    memcpy(f[i][j],p2,sizeof(p2));
    int temp[30];
    plusx(f[i][j],f[i][j],temp);
    memcpy(f[i][j],temp,sizeof(temp));
    // f[i][j]=max(a[k][i]+f[i+1][j-1],a[k][i+j-1]+f[i][j-1]);
    // f[i][j]*=2;
    }
    int re[30];
    plusx(sum,f[1][m],re);
    memcpy(sum,re,sizeof(re));
    }
    output(sum);
    return 0;
    }

  • 0
    @ 2016-02-13 15:46:09

    高精度
    #include<stdio.h>
    using namespace std;
    int n,m;
    int rec[81][81];
    int dp[81][81][21]; //dp[i][j]:maxscore of i~j in one low
    int inc[81][81];
    int sum[501]={0},suminc=1000000000;

    int min(int a,int b)
    {
    if(a<b) return a;
    else return b;
    }
    void update(int a,int b,int s,int t)
    {
    int i,cons=20;
    for(i=20;i>=inc[s][t];i--)
    dp[a][b][i]=dp[s][t][i]*2;

    inc[a][b]=inc[s][t];
    while(dp[a][b][cons]>=10000 || cons>inc[a][b])
    {
    dp[a][b][cons-1]+=dp[a][b][cons]/10000;
    dp[a][b][cons]%=10000;
    cons--;
    }
    inc[a][b]=min(inc[a][b],cons);
    }

    void check(int c,int a,int b)
    {
    int a1=a,a2=b-1,b1=a+1,b2=b,fi=inc[a1][a2],fj=inc[b1][b2],label1[21]={0},label2[21]={0},last1=20,last2=20,i,x;

    label1[20]=dp[a1][a2][20];label2[20]=dp[b1][b2][20];
    dp[a1][a2][20]+=rec[c][b];
    dp[b1][b2][20]+=rec[c][a];

    x=20;
    while(dp[a1][a2][x]>=10000)
    {
    label1[x-1]=dp[a1][a2][x-1];
    last1=x-1;
    dp[a1][a2][x-1]+= dp[a1][a2][x]/10000;
    dp[a1][a2][x]%=10000;
    x--;
    }
    if(x<inc[a1][a2]) inc[a1][a2]=x;

    x=20;
    while(dp[b1][b2][x]>=10000)
    {
    label2[x-1]=dp[b1][b2][x-1];
    last2=x-1;
    dp[b1][b2][x-1]+=dp[b1][b2][x]/10000;
    dp[b1][b2][x]%=10000;
    x--;
    }
    if(x<inc[b1][b2]) inc[b1][b2]=x;

    if(inc[a1][a2]<inc[b1][b2]) update(a,b,a1,a2);
    else if(inc[a1][a2]>inc[b1][b2]) update(a,b,b1,b2);
    else
    {
    x=inc[a1][a2];
    again:;
    if(dp[a1][a2][x]>dp[b1][b2][x]) update(a,b,a1,a2);
    else if(dp[a1][a2][x]<dp[b1][b2][x]) update(a,b,b1,b2);
    else{if(x!=20) {x++;goto again;} else update(a,b,a1,a2);}
    }

    for(i=last1;i<=20;i++) dp[a1][a2][i]=label1[i];
    for(i=last2;i<=20;i++) dp[b1][b2][i]=label2[i];
    inc[a1][a2]=fi;
    inc[b1][b2]=fj;

    }

    int main( )
    {

    int i,j,k,t,con;
    scanf("%d %d",&n,&m);

    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    scanf("%d",&rec[i][j]);

    for(i=1;i<=n;i++)
    {
    for(j=1;j<=m;j++)
    for(k=1;k<=m;k++)
    for(t=0;t<=20;t++)
    dp[j][k][t]=0;

    for(j=1;j<=m;j++)
    {
    dp[j][j][20]=rec[i][j]*2;
    inc[j][j]=20;
    }

    for(j=1;j<=m-1;j++)
    for(k=1;k<=m-j;k++)
    check(i,k,k+j);

    con=500;

    for(j=20;j>=inc[1][m];j--)
    sum[j+480]+=dp[1][m][j];

    suminc=min(suminc,inc[1][m]+480);

    while(sum[con]>=10000 || con>suminc)
    {
    sum[con-1]+=sum[con]/10000;
    sum[con]%=10000;
    con--;
    }

    suminc=min(con,suminc);

    }

    for(i=suminc;i<=500;i++)
    {
    if(i==suminc) printf("%d",sum[i]);
    else
    {
    if(sum[i]>=1000) printf("%d",sum[i]);
    else if(sum[i]>=100) printf("0%d",sum[i]);
    else if(sum[i]>=10) printf("00%d",sum[i]);
    else printf("000%d",sum[i]);
    }
    }

    return 0;
    }

  • 0
    @ 2015-09-11 12:42:59

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int MAXN = 85;
    const int N = 50;

    int m;
    int num[MAXN][MAXN], f[MAXN][MAXN][N+10], ming[MAXN][N+10];
    int ans[N], bri[N], bri1[N], bri2[N];

    void cheng1(int node){
    for(int i=1; i<=N; i++)
    ming[node][i] = ming[node-1][i] * 2;
    for(int i=1; i<=N; i++){
    ming[node][i+1] += ming[node][i]/10;
    ming[node][i] %= 10;
    }

    }

    void init1(int big){
    ming[1][1] = 2;
    for(int i=2; i<=big; i++)
    cheng1(i);
    }

    void init2(){
    memset(bri, 0, sizeof(bri));
    }

    void choice(int k, int a, int b){
    memset(bri1, 0, sizeof(bri1));
    memset(bri2, 0, sizeof(bri2));
    int q = m - b + a - 1;
    //
    for(int i=1; i<=N; i++)
    bri1[i] = ming[q][i] * num[k][a-1];
    for(int i=1; i<=N; i++){
    bri1[i+1] += bri1[i] / 10;
    bri1[i] %= 10;

    }
    for(int i=1; i<=N; i++){
    bri1[i] += f[a-1][b][i];
    bri1[i+1] += bri1[i] / 10;
    bri1[i] %= 10;
    }
    //
    for(int i=1; i<=N; i++)
    bri2[i] = ming[q][i] * num[k][b+1];
    for(int i=1; i<=N; i++){
    bri2[i+1] += bri2[i] / 10;
    bri2[i] %= 10;

    }
    for(int i=1; i<=N; i++){
    bri2[i] += f[a][b+1][i];
    bri2[i+1] += bri2[i] / 10;
    bri2[i] %= 10;
    }
    //
    int flag = 0;
    for(int i=N; i>=1; i--){
    if(bri1[i] > bri2[i]){
    flag = 1;
    break;
    }
    else if(bri1[i] < bri2[i]){
    flag = 2;
    break;
    }
    }
    if(flag == 1)
    for(int i=1; i<=N; i++)
    f[a][b][i] = bri1[i];
    else
    for(int i=1; i<=N; i++)
    f[a][b][i] = bri2[i];

    }

    void Lastcaculate(int k, int a){
    memset(bri1, 0, sizeof(bri1));
    for(int i=1; i<=N; i++)
    bri1[i] = ming[m][i] * num[k][a];
    for(int i=1; i<=N; i++){
    bri1[i+1] += bri1[i] / 10;
    bri1[i] %= 10;
    }
    for(int i=1; i<=N; i++){
    bri1[i] += f[a][a][i];
    bri1[i+1] += bri1[i] / 10;
    bri1[i] %= 10;
    }
    //
    int flag = 0;
    for(int i=N; i>=1; i--){
    if(bri[i] > bri1[i])
    return;
    else if(bri[i] < bri1[i]){
    flag = 1;
    break;
    }

    }
    if(flag)
    for(int i=1; i<=N; i++)
    bri[i] = bri1[i];
    }

    void jia(){
    for(int i=1; i<=N; i++){
    ans[i] += bri[i];
    ans[i+1] += ans[i] / 10;
    ans[i] %= 10;
    }
    }

    int main()
    {
    int n;
    scanf("%d%d", &n, &m);
    init1(m);
    for(int i=1; i<=n; i++)
    for(int j=1; j<=m; j++)
    scanf("%d", &num[i][j]);
    for(int k=1; k<=n; k++){
    init2();
    for(int i=1; i<=m; i++)
    for(int j=m; j>=i; j--)
    choice(k, i, j);
    for(int i=1; i<=m; i++)
    Lastcaculate(k, i);
    jia();
    }
    int len = 1;
    for(int i=N; i>=1; i--)
    if(ans[i] != 0){
    len = i;
    break;
    }
    for(int i=len; i>=1; i--)
    printf("%d", ans[i]);
    system("pause");

    return 0;
    }
    DP + 高精度 = AC

  • 0
    @ 2015-08-15 15:35:53

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 1800 KiB, score = 10

    测试数据 #1: Accepted, time = 15 ms, mem = 1800 KiB, score = 10

    测试数据 #2: Accepted, time = 15 ms, mem = 1800 KiB, score = 10

    测试数据 #3: Accepted, time = 31 ms, mem = 1800 KiB, score = 10

    测试数据 #4: Accepted, time = 31 ms, mem = 1800 KiB, score = 10

    测试数据 #5: Accepted, time = 62 ms, mem = 1796 KiB, score = 10

    测试数据 #6: Accepted, time = 125 ms, mem = 1800 KiB, score = 10

    测试数据 #7: Accepted, time = 453 ms, mem = 1796 KiB, score = 10

    测试数据 #8: Accepted, time = 609 ms, mem = 1796 KiB, score = 10

    测试数据 #9: Accepted, time = 1 ms, mem = 1800 KiB, score = 10

    Accepted, time = 1357 ms, mem = 1800 KiB, score = 100
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>

    struct bignum
    {
    int l;
    short int w[100];
    bignum()
    {
    l=1;
    memset(w,0,sizeof(w));
    };

    bignum(int x)
    {
    l=0;
    memset(w,0,sizeof(w));
    while(x!=0)
    {
    w[l]=x%10;
    x/=10;
    l++;
    }
    }

    bool operator >(bignum x)
    {
    if(l>x.l) return true;
    else if(l==x.l)
    for(int i=l-1;i>=0;i--)
    {
    if(w[i]>x.w[i]) return true;
    else if(w[i]<x.w[i]) return false;
    }
    return false;
    }

    bignum operator +(bignum x)
    {
    bignum ans;
    if(l>x.l) ans.l=l;
    else ans.l=x.l;
    for(int i=0;i<ans.l;i++)
    {
    ans.w[i]+=w[i]+x.w[i];
    ans.w[i+1]+=ans.w[i]/10;
    ans.w[i]=ans.w[i]%10;
    }
    if(ans.w[ans.l]!=0) ans.l++;
    return ans;
    }

    bignum operator*(bignum x)
    {
    bignum ans;
    ans.l=x.l+l;
    for(int i=0;i<l;i++)
    {
    for(int j=0;j<x.l;j++)
    {
    ans.w[i+j]+=w[i]*x.w[j];
    ans.w[i+j+1]+=ans.w[i+j]/10;
    ans.w[i+j]%=10;
    }
    }
    if(ans.w[ans.l-1]==0) ans.l--;
    return ans;
    }

    bignum operator*(int d)
    {
    bignum ans(d);
    return operator*(ans);
    }

    void print()
    {
    for(int i=l-1;i>=0 ;i--)
    printf("%d",w[i]);
    printf("\n");
    }
    };

    bignum max(bignum ta,bignum tb)
    {
    if(ta>tb) return ta;
    return tb;
    }

    int main()
    {
    static bignum two[80],ans;
    int n,m;
    scanf("%d%d",&n,&m);
    two[0]=1;
    for(int i=1;i<=m;i++)
    two[i]=two[i-1]*2;
    for(int i=0;i<n;i++)
    {
    int in[80];
    bignum dp[80][80];
    for(int j=0;j<m;j++)
    scanf("%d",&in[j]);
    for(int j=0;j<m;j++)
    dp[j][j]=two[m]*in[j];
    for(int j=m-2;j>=0;j--)
    for(int k=j+1;k<m;k++)
    dp[j][k]=max(dp[j][k-1]+two[m-k+j]*in[k],dp[j+1][k]+two[m-k+j]*in[j]);
    ans=ans+dp[0][m-1];
    }
    ans.print();
    return 0;
    }

  • 0
    @ 2014-10-28 18:35:39

    var x,y,l,i,j,k,m,n,p,q,t,s,max,head,tail:longint;
    a:array[0..300,0..300] of longint;
    vetex,dist:array[0..300,0..300] of longint;
    pre,way:array[0..300] of longint;
    ans:longint;
    v:array[0..300] of boolean;
    ok:boolean;
    procedure findway(a:longint);
    var i,j:longint;
    begin
    if ok then exit;
    if a=tail then begin ok:=true; exit; end;
    for i:=1 to vetex[a,vetex[a,0]] do
    if not v[vetex[a,i]] then
    begin
    v[vetex[a,i]]:=true;
    pre[vetex[a,i]]:=a;
    findway(vetex[a,i]);
    end;
    end;
    procedure ecc(h,t:longint);
    var i,j:longint;
    tem,sum:longint;
    begin
    sum:=0;
    for j:=1 to n do
    begin
    tem:=1000000;
    for i:=h to t do
    begin
    if (dist[way[i],j]<tem) and (dist[way[i],j]<1000000) then tem:=dist[way[i],j]; end; if sum<tem then sum:=tem; end; if sum<ans then ans:=sum; end; procedure floyed; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if (i<>j) and (i<>k) and (j<>k) and (dist[i,k]+dist[k,j]<dist[i,j]) then
    begin
    dist[i,j]:=dist[i,k]+dist[k,j];
    end;

    end;
    procedure work;
    begin
    for i:=1 to p do
    for j:=i to p do
    if (dist[way[i],way[j]]<=s) and (dist[way[i],way[j]]<1000000) then ecc(i,j); end; begin ans:=10000000; read(n,s); for i:=1 to n do for j:=1 to n do dist[i,j]:=1000000; for i:=1 to n do dist[i,i]:=0; for i:=1 to n-1 do begin read(x,y,l); dist[x,y]:=l; dist[y,x]:=l; inc(vetex[x,0]); vetex[x,vetex[x,0]]:=y; inc(vetex[y,0]); vetex[y,vetex[y,0]]:=x; end; floyed; for i:=1 to n do for j:=i+1 to n do if (dist[i,j]>max) and (dist[i,j]<100000) then
    begin
    max:=dist[i,j];
    head:=i;
    tail:=j;
    end;
    findway(head);
    pre[head]:=0;
    k:=tail;
    repeat
    inc(p);
    way[p]:=k;
    k:=pre[k];
    until k=0;
    work;
    writeln(ans);
    end.

  • 0
    @ 2014-10-28 11:02:46

    NOIP2014赛前AC留念
    (查了一上午的高精度……赛前还是要巩固一下基础算法啊……)
    type hugeint=record
    num:array[1..120] of integer;
    len:longint;
    end;
    var ans:hugeint;
    f:array[1..80,1..80,1..80] of hugeint;
    n,m,i,j,k:longint;
    tip,tt:array[0..80] of hugeint;
    a:array[1..80,1..80] of longint;
    zz:hugeint;

    function add(a,b:hugeint):hugeint;
    var temp,i:longint;
    begin
    for i:=1 to 120 do add.num[i]:=0;
    if a.len>b.len then temp:=a.len
    else temp:=b.len;

    for i:=1 to temp do
    add.num[i]:=a.num[i]+b.num[i];

    for i:=1 to temp do
    if add.num[i]>=10 then
    begin
    add.num[i+1]:=add.num[i+1]+add.num[i] div 10;
    add.num[i]:=add.num[i] mod 10;
    end;

    if add.num[temp+1]>0 then add.len:=temp+1
    else add.len:=temp;
    zz:=add;
    end;

    function plus(k:longint):hugeint;
    var i,j:longint;
    begin
    for i:=1 to 120 do plus.num[i]:=0;
    plus.len:=1;
    plus.num[1]:=1;
    zz:=plus;
    for i:=1 to k do
    begin
    for j:=1 to plus.len do
    plus.num[j]:=plus.num[j]*2;
    zz:=plus;
    for j:=1 to plus.len do
    begin
    plus.num[j+1]:=plus.num[j+1]+plus.num[j] div 10;
    plus.num[j]:=plus.num[j] mod 10;
    end;
    if plus.num[plus.len+1]>0 then inc(plus.len);
    end;
    zz:=plus;
    end;

    function cheng(k:longint;p:hugeint):hugeint;
    var i,qq:longint;
    s:string;
    begin
    zz:=p;
    for i:=1 to p.len do
    p.num[i]:=p.num[i]*k;
    str(k,s);
    qq:=length(S);
    for i:=1 to p.len+qq do
    begin
    if p.num[i]>=10 then
    begin
    p.num[i+1]:=p.num[i+1]+p.num[i] div 10;
    p.num[i]:=p.num[i] mod 10;
    end;
    end;

    for i:=p.len+qq+2 downto p.len do
    if p.num[i]>0 then
    begin
    p.len:=i;
    break;
    end;
    cheng:=p;
    zz:=p;
    end;

    function max(a,b:hugeint):hugeint;
    var i:longint;
    begin
    if a.len>b.len then exit(a);
    if b.len>a.len then exit(b);
    for i:=a.len downto 1 do
    begin
    if a.num[i]>b.num[i] then exit(a);
    if a.num[i]<b.num[i] then exit(b);
    end;
    exit(a);
    end;

    begin
    //assign(input,'t5.in');
    //assign(output,'t5.out');
    //reset(input);
    //rewrite(output);
    readln(n,m);
    for i:=1 to n do
    for j:=1 to m do read(a[i,j]);
    tip[0].len:=1;
    tip[0].num[1]:=0;
    for i:=1 to m do tip[i]:=plus(i);
    for i:=1 to n do
    begin
    tt[i].len:=0;
    f[i,1,m].len:=0;
    f[i,1,m].num[1]:=0;
    for j:=1 to m do
    for k:=m downto j do
    if m-k+j-1>0 then
    begin
    f[i,j,k].len:=0;
    f[i,j,k].num[1]:=0;
    if j-1>0 then
    f[i,j,k]:=max(add(f[i,j-1,k],cheng(a[i,j-1],tip[m-k+j-1])),f[i,j,k]);
    if k+1<=m then f[i,j,k]:=max(add(f[i,j,k+1],cheng(a[i,k+1],tip[m-k+j-1])),f[i,j,k]);
    end;
    zz:=cheng(a[i,1],tip[1]);
    zz:=cheng(a[i,3],tip[m]);
    zz:=f[i,2,3];
    for j:=1 to m do
    tt[i]:=max(add(f[i,j,j],cheng(a[i,j],tip[m])),tt[i]);
    end;
    for i:=1 to n do
    ans:=add(ans,tt[i]);
    for i:=ans.len downto 1 do
    write(ans.num[i]);
    writeln;
    //close(input);
    //close(output);
    end.

  • 0
    @ 2014-08-18 15:59:51

    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    struct bign
    {
    int dig,num[40];
    void init()
    {
    dig=1;
    memset(num,0,sizeof(num));
    }
    }f[90][90],_pow[90],ans;
    bign two=(bign){1,{0,2}};
    bign operator + (bign a,bign b)
    {
    int i;
    bign c;
    memset(c.num,0,sizeof(c.num));
    for(i=1;i<=(c.dig=max(a.dig,b.dig));i++)
    {
    c.num[i]+=a.num[i]+b.num[i];
    c.num[i+1]=c.num[i]/10;
    c.num[i]%=10;
    }
    if(c.num[c.dig+1]>0)
    c.dig++;
    return c;
    }
    bign operator * (bign a,bign b)
    {
    int i,j;
    bign c;
    memset(c.num,0,sizeof(c.num));
    for(i=1;i<=a.dig;i++)
    for(j=1;j<=b.dig;j++)
    c.num[i+j-1]+=a.num[i]*b.num[j];
    for(i=1;i<=(c.dig=a.dig+b.dig-1);i++)
    {
    c.num[i+1]+=c.num[i]/10;
    c.num[i]%=10;
    }
    if(c.num[c.dig+1]>0)
    c.dig++;
    return c;
    }
    bign operator * (bign a,int b)
    {
    int i;
    bign c;
    memset(c.num,0,sizeof(c.num));
    for(i=1;i<=a.dig;i++)
    c.num[i]+=a.num[i]*b;
    for(c.dig=1;;c.dig++)
    {
    c.num[c.dig+1]+=c.num[c.dig]/10;
    c.num[c.dig]%=10;
    if(c.num[c.dig+1]==0)
    break;
    }
    return c;
    }
    bign _max(bign a,bign b)
    {
    int i;
    if(a.dig>b.dig)
    return a;
    if(a.dig<b.dig)
    return b;
    for(i=a.dig;i>=1;i--)
    if(a.num[i]>b.num[i])
    return a;
    else
    if(a.num[i]<b.num[i])
    return b;
    return a;
    }
    main()
    {
    int n,m,a[90],i,j,r,c;
    cin>>n>>m;
    _pow[0]=(bign){1,{0,1}};
    for(i=1;i<=m;i++)
    _pow[i]=_pow[i-1]*two;
    for(r=1;r<=n;r++)
    {
    for(c=1;c<=m;c++)
    cin>>a[c];
    for(i=1;i<=m;i++)
    for(j=1;j<=m;j++)
    f[i][j].init();
    for(i=1;i<=m;i++)
    f[i][i]=_pow[m]*a[i];
    for(i=m-1;i>=1;i--)
    for(j=i+1;j<=m;j++)
    f[i][j]=_max(f[i+1][j]+_pow[m-j+i]*a[i],f[i][j-1]+_pow[m-j+i]*a[j]);
    ans=ans+f[1][m];
    }
    for(i=ans.dig;i>=1;i--)
    cout<<ans.num[i];
    }

  • 0
    @ 2014-04-18 22:40:16

    恶心的高精度。。

  • 0
    @ 2013-03-09 08:43:53

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;

    struct big{
    int d[200],l;
    void set(int x){for(int i=1;i<=l;i++)d[i]=0;d[1]=x;l=1;}
    int operatorconst{return d[t];}
    void operator+=(const big&o)
    {
    int v=0;l=max(l,o.l);
    for(int i=1;i<=l;i++)
    {
    v+=d[i]+o[i];
    d[i]=v%10;
    v/=10;
    }

    if(v)d[++l]=v;
    }
    void operator *=(int x)
    {
    int v=0;
    for(int i=1;i<=l;i++)
    {
    v+=d[i]*x;
    d[i]=v%10;
    v/=10;
    }
    while(v){
    d[++l]=v%10;
    v/=10;
    }
    }
    void print(){for(int i=l;i>0;i--)printf("%d",d[i]);printf("\n");}
    };

    big max(big x,big y)
    {
    if(x.l>y.l)return x;
    if(x.l<y.l)return y;
    for(int i=x.l;i>=0;i--){
    if(x.d[i]<y.d[i])return y;
    if(x.d[i]>y.d[i])return x;
    }
    return x;
    }

    int i,j,l,p,n,m,s,t;
    int a[100][100];
    big k[100],f[100][100],temp,ans,num,fl,fr;

    int main(){
    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;i++)
    {
    for(j=1;j<=m;j++)scanf("%d",&a[j][i]);
    scanf("\n");
    }
    k[0].set(1);
    for(i=1;i<=m+1;i++){k[i]=k[i-1];k[i]*=2;}
    for(p=1;p<=n;p++)
    {
    for(l=1;l<=m-1;l++)
    for(i=1;i<=l+1;i++)
    {
    s=i;t=m-(l-s+1);
    fl=f[s-1][l-1];temp=k[l];temp*=a[s-1][p];fl+=temp;
    fr=f[s][l-1];temp=k[l];temp*=a[t+1][p];fr+=temp;
    f[s][l]=max(fl,fr);

    }
    ans.set(0);
    for(i=1;i<=m;i++)
    {
    temp=k[m];temp*=a[i][p];
    temp+=f[i][m-1];
    ans=max(ans,temp);
    }

    num+=ans;

    }
    num.print();
    return 0;
    }

信息

ID
1378
难度
7
分类
动态规划 | 高精度 点击显示
标签
递交数
4517
已通过
1033
通过率
23%
被复制
8
上传者