1 条题解
-
0
可以比较简单的得到i的答案是从前面的状态转来的,所以可以很容易得出DP的方暴力代码(我考试的时候也就到这了),然后又因为 - 往前的状态转移过来后是一定不优于后面的状态转移过来的,所以第二层只需要 —— 即可
code:
#include<bits/stdc++.h> using namespace std; typedef long long ll; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } ll n,m; ll f[200005],a[200005]; ll ccf(ll i){ return i*i*i*i; } int main(){ freopen("bug.in","r",stdin); freopen("bug.out","w",stdout); lhhsyn(); cin>>n>>m; for(int i=1;i<=m;i++){ cin>>a[i]; } for(ll i=1;i<=m;i++){ f[i]=1e18; for(ll j=max(i-300,0ll);j<i;j++){ f[i]=min(f[i],f[j]+a[i]+ccf(i-j)); } } cout<<f[m]; return 0; }至于为什么i-300以前一定更不优:
我也不清楚qwq,我只打了80pts,后面是@songzirui和我说可以这样的
不过应该算算就行了,我考场上还是太懒了
- 1
信息
- ID
- 972
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 31
- 已通过
- 8
- 上传者