题解 P2134 【百日旅行】
xzyxzy
2018-02-07 09:05:07
表示楼下贪心很好，花样dp也不错，但好像都没我的短
正常90分都很容易想到，dp[0][i]表示到第i天且第i天还在旅行的最小代价
那么就是这样的90分
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
#define inf 100000000000000
using namespace std;
ll dp[2][200001],N,P,Q;
int main()
{
cin>>N>>P>>Q;
for(ll i=1;i<=N;i++)dp[0][i]=dp[1][i]=inf;
for(ll i=1;i<=N;i++)
for(ll j=0;j<i;j++)
{
dp[0][i]=min(dp[0][i],dp[1][j]+P*(i-j)*(i-j));
dp[1][i]=min(dp[1][i],dp[0][j]+Q*(i-j));
}
printf("%lld\n",min(dp[0][N],dp[1][N]));
return 0;
}
```
然后dp[1]的转移由于没有平方，那么很容易优化
至于dp[0]的优化，那就是若旅行花费还大于吃饭，那就吃饭去吧
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
#define inf 100000000000000
using namespace std;
ll dp[2][200001],N,P,Q，Min0;
int main()
{
cin>>N>>P>>Q;
for(ll i=1;i<=N;i++)dp[0][i]=dp[1][i]=inf;
for(ll i=1;i<=N;i++)
{
dp[1][i]=Min0+Q*i;
for(ll j=i;(i-j)*(i-j)<=Q&&j>=0;j--)
dp[0][i]=min(dp[0][i],dp[1][j]+P*(i-j)*(i-j));
Min0=min(Min0,dp[0][i]-Q*i);
}
printf("%lld\n",min(dp[0][N],dp[1][N]));
return 0;
}
```