我被卡住了几天,找wa点找了一个小时了......服气
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=6024
题目大意:
建小店,对没有小店的班级,去左边第一个小店
最后计算小店总花费+没有建店的班级去左边小店的路费
解题思路:
一开始想的是贪心,但当点最优实际上是算不出来的。
细想因为后面建店对前面红利有影响昂
所以dp【i】【j】,i 是当前序号,j 是建店与否
记得先对x排序
先把所以dp初始化为inf,(inf取1e18,因为1e8还小了*这个点wa多次好气)
然后求一下,i 作为店铺的时候,j 和之间的班级到 i 的路费之和(记做dis)
最后从 i 开始建店,把dp[i][1]都算一下
在这个 i 循环的里边,j从0取到i-1作为i左边的最近店铺,找到一家花费最少的店铺j
作为dp[i][0]
最后输出min(dp[n-1][0],dp[n-1][1])就行惹
AC代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
struct node{
int x,c;
}pt[3005];
bool cmp(node a,node b)
{
return a.x < b.x ;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
ll dis[n][n],dp[n][2];
for(int i=0;i<n;i++)
scanf("%d%d",&pt[i].x,&pt[i].c); //cin>>pt[i].x>>pt[i].c;
sort(pt,pt+n,cmp);
for(int i=0;i<n;i++)
{
dp[i][0]=inf;
dp[i][1]=inf;
dis[i][i]=0;
for(int j=i+1;j<n;j++)
dis[i][j]=dis[i][j-1]+pt[j].x-pt[i].x; //dis 小->大
//不是求教学楼之间的距离,而是当仅 i开店时,i+1~j都没开店,去i店的路费之和
}
dp[0][1]=pt[0].c; //最左边总要建店的
for(int i=1;i<n;i++)
{
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+pt[i].c; //我在i建店
for(int j=i-1;j>=0;j--) //我在i不建店,我左边一家店序号是j
dp[i][0]=min(dp[i][0],dp[j][1]+dis[j][i]);
}
ll ans=min(dp[n-1][0],dp[n-1][1]);
printf("%lld\n",ans);//cout<<min(dp[n-1][0],dp[n-1][1])<<endl;
}
return 0;
}
今天正好是成年两个月的日子诶
时间过得好快啊。
三顾 三省 无常