1 条题解

  • 0
    @ 2026-11-7 16:27:51

    可以比较简单的得到i的答案是从前面的状态转来的,所以可以很容易得出DP的nn方暴力代码(我考试的时候也就到这了),然后又因为 ii - 300300 往前的状态转移过来后是一定不优于后面的状态转移过来的,所以第二层只需要 i−300i-300 —— ii即可

    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

    [2026济南登峰营] D3 P3 代码调试(bug) - 文件读写

    信息

    ID
    972
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    31
    已通过
    8
    上传者