题意:给出n个物体的高度以及将他们高度改变1单位的花费,一个观测点从最左端从0往上走,一直平视. 问至少能观测到k个物体的最小花费.
因为高度比较大,所以需要将高度离散化,那么需要离散化哪些高度呢?容易发现对于每一个建筑,只要把它+-70范围内的高度离散化就好了,这样最多就是70*140种高度.然后用 dp[i][j][k] 表示到i物体,最大高度是j,一共看到k个物体的最小花费,转移式子就是
dp[i][j][k]=min{d.p[i−1][j′][k−1]+cost(j,hi)dp[i−1][j][k]+(j≤hi?cost(hi,j):0)(j′<j)(j′≥j)不难发现对于下面一半可以直接转移,对于上面一半可以维护一个最小值
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<stack> #include<cstring> #include<map> using namespace std; int p[105]; long long c[105]; vector<long long> h; int cnt; long long dp[75][75][14005]; long long inf=10000000000000000; long long cost(int id,int x) { long long h1=p[id]; long long h2=h[x]; long long ans=abs(h1-h2)*c[id]; return ans; } int main() { int n,k; while(~scanf("%d%d",&n,&k)) { h.clear(); p[0]=0; for(int i=1; i<=n; i++) { scanf("%d",&p[i]); //p[i]+=70; scanf("%lld",&c[i]); } cnt=0; for(int i=1; i<=n; i++) { for(int j=-70; j<=70; j++) { if((p[i]+j)>0){ h.push_back(p[i]+j); } } } sort(h.begin(), h.end()); h.erase(unique(h.begin(),h.end()),h.end()); cnt=h.size(); for(int i=1; i<=n; i++) { for(int l=0; l<=n; l++) { for(int j=0; j<cnt; j++) { dp[i][l][j]=inf; } } } for(int j=0; j<=141*n; j++) { dp[1][1][j]=cost(1,j); } for(int i=2;i<=n;i++) { for(int l=1;l<=n;l++) { long long minn=dp[i-1][l-1][0]; for(int j=0;j<cnt;j++) { if(p[i]>h[j]) { dp[i][l][j]=min(dp[i][l][j],dp[i-1][l][j]+cost(i,j)); } else dp[i][l][j]=min(dp[i][l][j],dp[i-1][l][j]); if(j!=0&&l!=1) { dp[i][l][j]=min(dp[i][l][j],minn+cost(i,j)); minn=min(minn,dp[i-1][l-1][j]); } //cout<<i<<" "<<l<<" "<<j<<" "<<dp[i][l][j]<<endl; } } } long long ans=inf; for(int j=0;j<cnt;j++) { for(int l=k;l<=n;l++) ans=min(dp[n][l][j],ans); } cout<<ans<<endl; } }
