5 6 2 8 7 1 0 5 2 10 20 0
10HintIn 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.
官方题解：
思路和官方是一样的，但是比赛时还是没 写出来，比赛后修修改改就过了，好忧桑啊.....
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef __int64 ll;
ll org[5010],l[5010],r[5010];
ll val[5010],d[2510];
struct node
{
int l,r;
} pos[5010];
map<ll,int>m;
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
m.clear();
for(int i=1; i<=n; i++)
{
scanf("%d",&org[i]);
if(i==1)
l[i]=org[i];
else l[i]=l[i-1]+org[i];
m[l[i]]=i;
}
int k=1,flag=1;
pos[0].l=pos[0].r=0;
for(int i=n; i>=1; i--)
{
if(i==n)
r[i]=org[i];
else r[i]=r[i+1]+org[i];
if(flag&&m.find(r[i])!=m.end())
{
pos[k].l=m[r[i]];
pos[k].r=n-i+1;
if(pos[k].l+pos[k].r>=n)
{
flag=0;
}
k++;
}
}
k--;
/*for(int i=0;i<=k;i++)
{
printf("l:%d r:%d\n",pos[i].l,pos[i].r);
}
*/
int mid;
if(pos[k].l+pos[k].r==n)
{
mid=0;
}
else
{
k--;
mid=n-pos[k].r-pos[k].l;
}
//printf("k:%d mid:%d\n",k,mid);
val[0]=0;
for(int i=1; i<=n; i++)
{
scanf("%I64d",&val[i]);
}
ll ans=-1;
d[0]=0;
for(int i=1; i<=k; i++)
{
d[i]=val[pos[i].l]+val[pos[i].r];
for(int j=1; j<i; j++)
{
d[i]=min(d[j]+val[pos[i].l-pos[j].l]+val[pos[i].r-pos[j].r],d[i]);
}
}
for(int i=0; i<=k; i++)
{
if(ans==-1||ans>d[i]+val[mid+pos[k].l-pos[i].l+pos[k].r-pos[i].r])
ans=d[i]+val[mid+pos[k].l-pos[i].l+pos[k].r-pos[i].r];
}
printf("%I64d\n",ans);
}
return 0;
}
hdu 4960 Another OCD Patient,布布扣,bubuko.com
原文：http://blog.csdn.net/knight_kaka/article/details/38686127