推销别人做网站有什么作用/友情链接价格

做法其实挺多的，显然我们可以维护一个下凸包，然后做斜率优化dp。

其次因为代价是平方的，所以一定不会连续太长，所以我们可以dp[i][0/1]去dp。每次最多往前转移1000个值。

然后我们也可以贪心去做，如果我们知道当前的旅行和吃饭天数，那么显然我们旅行肯定是平均的插入到吃饭之间。

然后因为这个是具有三分性的，我们可以对上面的结论三分。

第二种代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int dp[N][2],n,p,q;
signed main(){cin>>n>>p>>q;	memset(dp,0x3f,sizeof dp);dp[0][0]=dp[0][1]=0;for(int i=1;i<=n;i++){dp[i][0]=min(dp[i-1][0],dp[i-1][1])+q;for(int j=i-1,k=0;j>=0&&k<1000;j--,k++)	dp[i][1]=min(dp[i][1],dp[j][0]+p*(i-j)*(i-j));}cout<<min(dp[n][0],dp[n][1]);return 0;
}

第四种代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,p,q,res=1e18;
inline int check(int mid){int tmp=n-mid+1,bk=mid/tmp;return (tmp-1)*q+(mid%tmp)*(bk+1)*(bk+1)*p+(tmp-mid%tmp)*bk*bk*p;
}
signed main(){cin>>n>>p>>q;int l=0,r=n;while(l+10<r){int midl=l+(r-l)/3,midr=r-(r-l)/3;if(check(midl)<=check(midr))	r=midr;else	l=midl;}for(int i=l;i<=r;i++)	res=min(res,check(i));cout<<res;return 0;
}