题目链接:hdu 4960

题意:一排橡皮泥排成一排,要求最后捏成对称的,捏过的不能再捏.

思路:书读的少啊!!!看到题就想暴力,发现不行才想dp,状态转移方程dp[j]=min(dp[j],dp[i]+a[cnt]),初始化dp值为从开始捏到I.

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 100010
#define INF 1e9
struct node{
int x,y;
node(){}
node(int xe,int ye):x(xe),y(ye) {}
};
int  data[MAXN],a[MAXN];
int n;
int dp[MAXN];
vector <node>  layer;
void init()
{
layer.clear();
for(int i=0;i<n;i++)
{
scanf("%d",&data[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
a[0]=0;
}
int be_layer()
{
int l=0,r=n-1,ans;
int x,y;
long long l_value,r_value;
x=1,y=1,l_value=data[0],r_value=data[n-1];
while(1)
{
if(l_value>r_value)
{
y++;
r--;
r_value+=data[r];
}
else if(l_value<r_value){
x++;
l++;
l_value+=data[l];
}
else {
// cout<<l<<" x "<<r<<endl;
if(l>=r)
{
//
ans=y;
break;
}
//cout<<l_value<<" "<<r_value<<endl;
//  printf("%d %d\n",x,y);
layer.push_back(node(x,y));
if(l+1==r)
{
ans=0;
break;
}
r--;
l++;
x=1,y=1,l_value=data[l],r_value=data[r];
}
}
return ans;
}
void slove()
{
int midcnt=be_layer();
//cout<<midcnt<<endl;
dp[0]=0;
int sizee=layer.size();
//cout<<midcnt<<" "<<sizee<<endl;
for(int i=0;i<sizee;i++)
// cout<<layer[i].x<<" "<<layer[i].y<<endl;
for(int i=1;i<=sizee;i++)
{
dp[i]=INF;
}
int sum_l=0,sum_r=0;
for(int j=0;j<sizee;j++)
{
sum_l+=layer[j].x;
sum_r+=layer[j].y;
dp[j]=(a[sum_l]+a[sum_r]);
}
for(int i=0;i<sizee;i++)
{
sum_l=0,sum_r=0;
for(int j=i+1;j<sizee;j++)
{
sum_l+=layer[j].x;
sum_r+=layer[j].y;
dp[j]=min(dp[j],dp[i]+a[sum_l]+a[sum_r]);
}
}
int ans=INF;
for(int i=sizee-1;i>=0;i--)
{
if(ans>dp[i]+a[midcnt])
{
ans=dp[i]+a[midcnt];
}
if(i)
{
midcnt+=(layer[i].x+layer[i].y);
}
}
if(sizee==0) ans=a[n];
printf("%d\n",ans);
}
int main()
{
//freopen("1001.in","r",stdin);
//freopen("data.out","w",stdout);
while(1){
scanf("%d",&n);
if(n==0) break;
init();
slove();
}
return 0;
}