HDU 4960(또 다른 OCD 환자 구간 dp)
5847 단어 dp
Problem Description 은 하나의 수열 을 알 고 있 습 니 다.이 제 는 k 세그먼트 로 나 누 어 각 세그먼트 와 구 성 된 새로운 수열 의 답문 을 요구 하고 합병 대가 가 가장 적 습 니 다.합병의 대 가 는∑ki=1a[len](len 은 이 단락 의 길이)
Input The input contains multiple test cases.
The first line of each case is an integer N (0 < N <= 5000), indicating the number of pieces in a line. The second line contains N integers Vi, volume of each piece (0 < Vi <=10^9). The third line contains N integers ai (0 < ai <=10000), and a1 is always 0.
The input is terminated by N = 0.
Output Output one line containing the minimum cost of all operations Xiaoji needs.
Sample Input 5 6 2 8 7 1 0 5 2 10 20 0
Sample Output 10
HintIn the sample, there is two ways to achieve Xiaoji’s goal. [6 2 8 7 1] -> [8 8 7 1] -> [8 8 8] will cost 5 + 5 = 10. [6 2 8 7 1] -> [24] will cost 20.
Author SYSU
Source 2014 Multi-University Training Contest 9
Recommend We have carefully selected several similar problems for you: 5431 5430 5429 5428 5427
#include<bits/stdc++.h>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define MAXN (5000+10)
typedef __int64 ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n,a[MAXN],v[MAXN];
ll s[MAXN],s2[MAXN];
int l[MAXN],r[MAXN],tot=0;
ll cost[MAXN];
int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
while(scanf("%d",&n)&&n) {
For(i,n) scanf("%d",&v[i]);
For(i,n) scanf("%d",&a[i]); a[0]=0;
s[0]=s2[n+1]=0;
For(i,n) s[i]=s[i-1]+(ll)v[i];
ForD(i,n) s2[i]=s2[i+1]+(ll)v[i];
tot=0;
int fro=1,tail=n;
while(fro<tail) {
if (s[fro]==s2[tail]) {
l[++tot]=fro;
r[tot]=tail;
fro++,tail--;
} else if (s[fro]<s2[tail]) ++fro;
else --tail;
}
MEMI(cost)
l[0]=0,r[0]=n+1; cost[0]=0;
ll ans=a[n];
For(i,tot) {
Rep(j,i) {
cost[i]=min(cost[i],cost[j]+a[l[i]-l[j]]+a[r[j]-r[i]]);
}
ans=min(ans,cost[i]+a[r[i]-1-l[i]]) ;
}
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.