#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;
const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
struct segment_tree_1
{
int l,r,mid,x;
}st[2*64+2];
int n,m;
int a[50+1];
int p[50+1];
int f[50+1][50+1][1+1];
void build_segment_tree_1(int now,int l,int r)
{
st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2;
if (l<r)
{
if (l<=st[now].mid)
build_segment_tree_1(now*2,l,st[now].mid);
if (st[now].mid+1<=r)
build_segment_tree_1(now*2+1,st[now].mid+1,r);
}
if (l==r)
st[now].x=p[l];
else
st[now].x=st[now*2].x+st[now*2+1].x;
}
int sum_1(int now,int l,int r)
{
if (l>r)
return 0;
else if (st[now].l==l&&r==st[now].r)
return st[now].x;
else if (r<=st[now].mid)
return sum_1(now*2,l,r);
else if (st[now].mid+1<=l)
return sum_1(now*2+1,l,r);
else
return sum_1(now*2,l,st[now].mid)+sum_1(now*2+1,st[now].mid+1,r);
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i],&p[i]);
build_segment_tree_1(1,1,n);
memset(f,oo_max,sizeof(f));
f[m][m][0]=f[m][m][1]=0;
for (int l=1;l<=n;l++)
for (int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[i+1]-a[i]));
f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[j]-a[i]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[i]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[j-1]));
}
printf("%d\n",min(f[1][n][0],f[1][n][1]));
}
}
是数据没有51但你f数组用到了51吧。
还有为啥要写线段树啊直接前缀和不行吗
數據不是51那f為啥會用到了51?
我寫綫段樹只是練練手
哦,我知道了
f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[i+1]-a[i]));
f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[j]-a[i]));
好吧是數據範圍51,寫一個50來坑我
AC
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;
const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;
struct segment_tree_1
{
int l,r,mid,x;
}st[2*64+2];
int n,m;
int a[51+1];
int p[51+1];
int f[51+1][51+1][1+1];
void build_segment_tree_1(int now,int l,int r)
{
st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2;
if (l<r)
{
if (l<=st[now].mid)
build_segment_tree_1(now*2,l,st[now].mid);
if (st[now].mid+1<=r)
build_segment_tree_1(now*2+1,st[now].mid+1,r);
}
if (l==r)
st[now].x=p[l];
else
st[now].x=st[now*2].x+st[now*2+1].x;
}
int sum_1(int now,int l,int r)
{
if (l>r)
return 0;
else if (st[now].l==l&&r==st[now].r)
return st[now].x;
else if (r<=st[now].mid)
return sum_1(now*2,l,r);
else if (st[now].mid+1<=l)
return sum_1(now*2+1,l,r);
else
return sum_1(now*2,l,st[now].mid)+sum_1(now*2+1,st[now].mid+1,r);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i],&p[i]);
build_segment_tree_1(1,1,n);
memset(f,oo_max,sizeof(f));
f[m][m][0]=f[m][m][1]=0;
for (int l=1;l<=n;l++)
for (int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[i+1]-a[i]));
f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(sum_1(1,1,n)-sum_1(1,i+1,j))*(a[j]-a[i]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[i]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(sum_1(1,1,n)-sum_1(1,i,j-1))*(a[j]-a[j-1]));
}
printf("%d\n",min(f[1][n][0],f[1][n][1]));
}