- 「一本通 5.1 例 3」凸多边形的划分
暂存
-
C23panweiming
LV 6
@
2025-5-7 14:00:51
#include <bits/stdc++.h>
using namespace std;
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 write(__int128 x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
__int128 get_min(__int128 x,__int128 y)
{
if(x<=y)
return x;
else
return y;
}
__int128 dp[105][105];
__int128 a[105];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
a[i]=read();
for(int len=3;len<=n;++len)
{
for(int i=1;i<n;++i)
{
int j=i+len-1;
if(j>n)
break;
dp[i][j]=dp[i][i+1]+dp[i+1][j]+a[i]*a[i+1]*a[j];
for(int k=i+2;k<j;++k)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);
}
}
__int128 mi=dp[1][n];
write(mi);
return 0;
}
1 comments
-
C23huangyuran LV 6 @ 2025-5-8 13:38:15pwm怎么还没做出来呀？
#include<iostream> #define longest __int128 using namespace std; istream&operator>>(istream&in,__int128&a){ a=0; string temp; in>>temp; int porn=1,len=temp.size(); if(temp[0]=='-'){ temp=temp.substr(1,len-1); len--; porn=-1; } for(int i=0;i<len;i++){ a+=temp[i]-'0'; a*=10; } a/=10; a*=porn; return in; } ostream&operator<<(ostream&out,__int128 a){ string temp; if(a==0){ out<<0; return out; } if(a<0){ out<<"-"; a=-a; } while(a){ temp=char(a%10+'0')+temp; a/=10; } out<<temp; return out; } int main(){ short n; cin>>n; longest a[2*n+1]; for(int i=1;i<=n;i++) cin>>a[i],a[n+i]=a[i]; longest f[2*n+1][2*n+1]; for(int i=1;i<=2*n-2;i++) f[i][i+2]=a[i]*a[i+1]*a[i+2]; for(int l=4;l<=n;l++) for(int i=1;i+l-1<=2*n;i++){ int j=i+l-1; f[i][j]=a[i]*a[j]*a[i+1]+f[i+1][j]; for(int k=i+2;k<=j-1;k++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]*a[j]*a[k]); } longest ans=f[1][n]; for(int i=2;i<=n;i++) ans=min(ans,f[i][i+n-1]); cout<<ans; return 0; }
- 1
