1 solutions
-
0
Guest MOD
-
0
非常简单
#include<bits/stdc++.h> using namespace std; int a[305]; int dp[305][305]; int dpm[305][305]; int n; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } for(int i=1;i<=2*n;i++){ a[i]=a[i-1]+a[i]; } for(int i=2;i<=n;i++){ for(int j=1;j<=n*2-i+1;j++){ dp[j][j+i-1]=INT_MAX; for(int k=j;k<j+i-1;k++){ dp[j][j+i-1]=min(dp[j][k]+dp[k+1][j+i-1]+a[j+i-1]-a[j-1],dp[j][j+i-1]); dpm[j][j+i-1]=max(dpm[j][k]+dpm[k+1][j+i-1]+a[j+i-1]-a[j-1],dpm[j][j+i-1]); } } } int ans1=INT_MAX; int ans2=0; for(int i=1;i<=n;i++){ int j=i+n-1; ans1=min(ans1,dp[i][j]); ans2=max(ans2,dpm[i][j]); } cout<<ans1<<endl; cout<<ans2; }
Information
- ID
- 49
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 17
- Accepted
- 6
- Uploaded By