这叫区间dp?
by 很性感的人 @ 2017-09-20 19:23:27
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
struct book
{
int w,h;
}a[110];
int n,k,f[110][110][110],sum[110];
bool cmp(book b1,book b2){return b1.h<b2.h;}
int main()
{
memset(f,0x7f,sizeof f);
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].w);
sort(a+1,a+n+1,cmp);
for (int i=1;i<=n;i++) f[i][i][0]=0;
for (int i=2;i<=n;i++) sum[i]=sum[i-1]+abs(a[i].w-a[i-1].w);
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++) f[i][j][0]=sum[j]-sum[i];
for (int p=1;p<=k;p++) //p是拿掉的书有p本
for (int i=1;i<n;i++) //左端点
for (int j=i+1;j<=n;j++) //右端点
for (int q=i;q<=j;q++) //拿掉第q个
{
if (q>i && q<j)
{
for (int ii=0;ii<=p-1;ii++)
f[i][j][p]=min(f[i][q-1][ii]+f[q+1][j][ii]+abs(a[q+1].w-a[q-1].w),f[i][j][p]);
}
else if (q==i)
f[i][j][p]=min(f[i][j][p],f[i+1][j][p-1]);
else if (q==j)
f[i][j][p]=min(f[i][j][p],f[i][j-1][p-1]);
}
printf("%d",f[1][n][k]);
return 0;
}
```
by syh0313 @ 2017-10-19 16:23:38
楼上哪里有错区间dp（忽略复杂度）
by syh0313 @ 2017-10-19 16:24:31
最后写了一个和std对拍有几个点不同的代码
结果A了、、、
```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,k,f[110][110],ans=20000313,b[210];
struct book
{
int w,h;
}a[110];
bool cmp(book b1,book b2){return b1.h<b2.h;}
int main()
{
freopen("dp.in","r",stdin);
freopen("dp.out","w",stdout);
scanf("%d%d",&n,&k);
if (n==k || n==k+1) {printf("0"); return 0;}
for (int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].h,&a[i].w);
b[a[i].w]++;
if (b[a[i].w]==n-k) {printf("0"); return 0;}
}
sort(a+1,a+n+1,cmp);
memset(f,0x7f,sizeof f);
for (int i=1;i<=n;i++) f[i][1]=0;
for (int p=2;p<=n-k;p++)
for (int i=2;i<=n;i++)
for (int j=1;j<i;j++)
f[i][p]=min(f[i][p],f[j][p-1]+abs(a[j].w-a[i].w));
for (int i=k;i<=n;i++) ans=min(ans,f[i][n-k]);
printf("%d",ans);
return 0;
}
```
by syh0313 @ 2017-10-20 16:26:00
@[友邻牧鸡](/space/show?uid=21192)
@ [友邻牧鸡](/space/show?uid=21192)
by syh0313 @ 2017-10-23 08:32:36
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 105
using namespace std;
int n,k;
struct Book{int h,w;}a[maxn];
int f[maxn][maxn];
int abs(int x){return x<0?-x:x;}
int dfs(int now,int cnt,int xuan){
if(f[now][cnt]!=-1) return f[now][cnt];
int ans=19260817;
if(now==n) return 0;
if(n-xuan==k) return 0;
if(cnt==k) return f[now][cnt]=dfs(now+1,cnt,xuan+1)+abs(a[now+1].w-a[now].w);
for(int i=1;i<=n;i++)
if(now+i<=n&&cnt+(i-1)<=k) ans=min(ans,dfs(now+i,cnt+(i-1),xuan+1)+abs(a[now+i].w-a[now].w));
return f[now][cnt]=ans;
}
bool cmp(Book aaa,Book bbb){return aaa.h<bbb.h;}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].h,&a[i].w);
sort(a+1,a+n+1,cmp);
memset(f,-1,sizeof(f));
int ans=19260817;
for(int i=1;i<=k+1;i++){
ans=min(ans,dfs(i,i-1,1));
}
printf("%d",ans);
return 0;
}
by zhouzhengye @ 2019-06-05 23:01:25