AcWing 1069. 不想写高精度之__int128    原题链接    中等

作者： 作者的头像   Perf ,  2021-07-22 13:55:03 ,  所有人可见 ,  阅读 661

4


2

算法1：区间DP

emmmm不想写高精度了，那就用__int128来代替吧。

对于__int128,只能在Linux的编译环境下使用。而且，cin和cout都是无法操作的。因此需要自己整一套快读快写的模板，如下：

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 110
typedef __int128 LL;

LL s[MAXN];
int n;
LL f[MAXN][MAXN];

inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

int main(){
    cin >> n ;
    for(int i=1;i<=n;i++){s[i]=read(); s[i+n]=s[i];}

    memset(f,0x3f,sizeof f);

    for(int len=1;len<=n;len++){
        for(int i=1;i+len-1<=2*n;i++){
            int l=i,r=len+i-1;
            if(len<=2) f[l][r]=0;
            else if(len==3) f[l][r]=s[l]*s[l+1]*s[l+2];
            else
                for(int k=l;k<=r;k++){
                    f[l][r]=min(f[l][r],f[l][k]+f[k][r]+s[l]*s[k]*s[r]);
                }
        }
    }
    LL u=1e31;
    for(int i=1;i<=n;i++)
        u=min(u,f[i][i+n-1]);
    print(u);

    return 0;
}

7 评论

用户头像
OnjoujiToki   2022-04-04 12:50         踩      回复

做到这题的时候就往题解去找看看int128能不能过。。2022年了真的不想写高精度了

用户头像
一只快乐的野指针   2022-02-14 17:11         踩      回复

大佬我想请教以下 为啥用y总的方法 只是换了个__int128就报错（样例都过不去）
呜呜呜呜呜之前都是老老实实写结构体板子（嘿嘿嘿嘿我要偷懒）

用户头像
Perf   2022-02-15 11:19      1    踩      回复

__int128要换一套自己写的输入输出的板子，正常的读入输出是不行的

用户头像
一只快乐的野指针   2022-02-15 13:23    回复了 Perf 的评论         踩      回复

我用了的 但是就是不行非得换成环形dp的写法 就是2 * n的这种

用户头像
Perf   2022-02-15 14:42    回复了 一只快乐的野指针 的评论         踩      回复

那你应该是模数的处理那里写的有问题

用户头像
einekleine1   2022-06-05 16:09         踩      回复

可以的，你f[l][r]赋的最大值的是不是小了

用户头像
einekleine1   2022-06-05 16:10         踩      回复 
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x&-x)
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
const ld eps=1e-6;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
namespace INT128{
    void scan(__int128 &x){
        int s=1;
        x=0;
        char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')s=-1;ch=getchar();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
        x*=s;
    }
    void print(__int128 x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9) print(x/10);
        putchar(x%10+'0');
    }
};
using namespace INT128;
int n;
__int128 w[55],f[55][55];
__int128 maxn=1e30;
int main(){
    //freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
    // ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    rep(i,1,n) scan(w[i]);
    rep(len,3,n)
        rep(l,1,n-len+1){
            int r=l+len-1;
            f[l][r]=maxn;
            rep(k,l+1,r-1)
                f[l][r]=min(f[l][r],f[l][k]+f[k][r]+w[l]*w[r]*w[k]);
        }
    print(f[1][n]);
    return 0;
}