QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#775545#9475. Pangu and Stonessurenjamts#AC ✓94ms12820kbC++201.5kb2024-11-23 16:11:142024-11-23 16:11:15

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 16:11:15]
  • 评测
  • 测评结果:AC
  • 用时:94ms
  • 内存:12820kb
  • [2024-11-23 16:11:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int n,l,r;
    while(cin>>n>>l>>r){
        vector<vector<vector<int>>> dp(n+5,vector<vector<int>> (n+5, vector<int> (n+5,1e18)));
        vector<int> a(n+1);
        vector<int> pref(n+1);
        for(int i=1; i<=n; i++){
            cin>>a[i];
            pref[i]=pref[i-1]+a[i];
        }
        for(int i=1; i<=n; i++){
            dp[i][i][1]=0;
        }
        for(int i=2; i<=n; i++){
            for(int j=1; j<=n; j++){
                int lo=j, hi=lo+i-1;
                if(hi>n) continue;
                dp[lo][hi][i]=0;
                for(int q=2; q<=i; q++){
                    for(int k=lo; k<hi; k++){
                       // for(int q=2; q<i; q++){
                            if(k+1<=hi)dp[lo][hi][q]=min(dp[lo][hi][q],dp[lo][k][1]+dp[k+1][hi][q-1]);
                           // if(k+1<=hi)dp[lo][hi][i]=min(dp[lo][hi][i],dp[lo][k][q]+dp[k+1][hi][i-q]+pref[hi]-pref[lo-1]);
                            if(l<=q and q<=r){
                                dp[lo][hi][1]=min(dp[lo][hi][1],dp[lo][hi][q]+pref[hi]-pref[lo-1]);
                            }
                       // }
                    }
                }
            }
        }
        //for(int i=1; i<=n; i++){
       //     for(int j=i; j<=n; j++){
         //       if(dp[i][j][1]!=1e18) cout<<i<<" "<<j<<" "<<dp[i][j][1]<<endl;
        //    }
      //  }
        if(dp[1][n][1]==1e18) cout<<0<<'\n';
        else cout<<dp[1][n][1]<<'\n';
    }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3544kb

input:

3 2 2
1 2 3
3 2 3
1 2 3
4 3 3
1 2 3 4

output:

9
6
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 94ms
memory: 12820kb

input:

100 4 7
570 608 194 26 243 470 418 119 1000 936 440 302 797 155 676 283 869 60 959 793 158 397 808 656 379 316 485 854 753 280 543 435 756 822 106 561 402 347 99 739 8 682 834 549 812 32 338 765 699 575 575 785 171 504 335 113 284 612 276 518 835 677 865 900 687 48 859 179 343 318 626 812 523 11 400...

output:

120446
66473
51039
85346
94828
7238
1564
8723
2852
15764
4266
8950
13004
1617
7620
5699
13659
922
6649
15773
3982
13002
12870
10934
2617
5941
3725
2246
6745
0
14698
10875
7909
9886
36014
4659
8894
0
8017
8860
10726
1144
4294
10730
4830
5373
10102
1623
12988
15216
900
11084
10326
8190
9628
1871
0
448...

result:

ok 105 lines