hdu 1300 Pearls（DP）

本文主要是介绍hdu 1300 Pearls（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

/*    就这道题而言;如果不用优化那么他是时间复杂度是 （O（n*n））  dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i]) 如果  有  k<j<i使得   dp[k]+(sum[i]-sum[k]+10)*p[i]>dp[j]+(sum[i]-sum[j]+10)*p[i];化简    dp[k]-dp[j]>(sum[k]-sum[j])*p[i];    这时j比k花费小 其中   另左边为  dy,右边为dx  则方程就是  dy>dx*p[i]; */
#include<stdio.h>
#include<string.h>
#include<algorithm>using namespace std;
const int maxn=105;
const int inf=1e9;
int dp[maxn],a[maxn],p[maxn],q[maxn];
int DP(int i,int j)
{return dp[j]+(a[i]-a[j]+10)*p[i]; //函数要自己推 
}
int dy(int i,int j){return dp[i]-dp[j];//函数要自己推 
}
int dx(int i,int j){return a[i]-a[j];//函数要自己推 
}
int main(){int T,min,i,j,c;scanf("%d",&T);while(T--){scanf("%d",&c);a[0]=0;int temp;for(i=1;i<=c;i++){scanf("%d%d",&temp,&p[i]);a[i]=a[i-1]+temp;}memset(dp,0,sizeof(dp));int l,r;l=r=0;//利用二分思想； q[r++]=0;for(i=1;i<=c;i++){while(l+1<r&&dy(q[l+1],q[l])<=p[i]*dx(q[l+1],q[l]))l++;dp[i]=DP(i,q[l]);while(l+1<r&&dy(i,q[r-1])*dx(q[r-1],q[r-2])<=dy(q[r-1],q[r-2])*dx(i,q[r-1]))r--;q[r++]=i;       }printf("%d\n",dp[c]);}return 0;
}

这篇关于hdu 1300 Pearls（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---