QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671823#9475. Pangu and Stoneszwu2021016337AC ✓76ms13968kbC++202.8kb2024-10-24 14:35:512024-10-24 14:35:53

Judging History

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

  • [2024-10-24 14:35:53]
  • 评测
  • 测评结果:AC
  • 用时:76ms
  • 内存:13968kb
  • [2024-10-24 14:35:51]
  • 提交

answer

#include <bits/stdc++.h> // By Lucky Ox
#define int long long
#define endl "\n"
#define pii pair<int, int>
#define PI atan(1.0) * 4
using namespace std;
using i128 = __int128;
typedef unsigned long long ull;
const int mod = LONG_LONG_MAX, INF = 0x3f3f3f3f3f3f3f3f;
int P(int x, int p){ return (x % p + p) % p; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int len_10(int x) { int len = 0; while(x) { x /= 10; len ++ ; } return len; }
int q_pow(int a, int k, int p) { int res = 1; while (k) { if (k & 1) res = res * a % p; k >>= 1; a = a * a % p; } return res; }
int to_int(string s) { int val = 0; for(int i = 0; i < (int)s.size(); i ++ ){val *= 10; val += s[i] - '0';}return val;}//注意:s是空串也会返回0
i128 read() { i128 x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar(); } return x; } //i128输入
void print(i128 x) {if(x > 9) print(x / 10); putchar(x % 10 + '0'); }//i128输出
//用__lg()来求一个数二进制下的位数 返回的len 表示这个数是[0, 1, ...., len] 比如10 __lg(10) = 3, 1010 [3, 2, 1, 0]
//__builtin_popcountll(int x) 求二进制下x中1的数量 __buitlin_ctzll(int x) 求二进制下末尾0的个数
//(n & (1 << i))的值可能会是1, 2, 4...... (n >> i) & 1的值一定是1
//将x转换成[1, n]中对应的数 (x - 1) % n + 1
//bool __ED__;
const int N = 1e2 + 10;
int n, l, r;
int a[N], s[N];
int dp[N][N][N]; // 元素数量为k 区间i,j的最小花费
signed main() {
    //cerr << abs(&__ED__-&__ST__) / (1024.0 * 1024.0) <<" MiB\n";
    ios::sync_with_stdio(0);cin.tie(0);
    cout << fixed << setprecision(10);
    while(cin >> n >> l >> r) {
        for(int i = 1; i <= n; i ++ ) cin >> a[i], s[i] = s[i - 1] + a[i];

        memset(dp, 0x3f, sizeof dp);
        for(int i = 1; i <= n; i ++ ) dp[1][i][i] = 0;

        for(int len = 2; len <= n; len ++ ) {
            for(int i = 1; i + len - 1 <= n; i ++ ) {
                int j = i + len - 1;
                for(int k = len; k >= 1; k -- ) {
                    if(k == 1) {
                        for(int cj = l; cj <= r; cj ++ ) {
                            dp[k][i][j] = min(dp[k][i][j], dp[cj][i][j] + s[j] - s[i - 1]);
                        }
                    }
                    else {
                        for(int cj = i; cj <= j - 1; cj ++ ) {
                            dp[k][i][j] = min(dp[k][i][j], dp[1][i][cj] + dp[k - 1][cj + 1][j]);
                        }
                    }
                }
            }
        }
        if(dp[1][1][n] >= 0x3f3f3f3f3f) cout << 0 << endl;
        else cout << dp[1][1][n] << endl;
    }
    return 0;
}
/*
3 2 2
1 2 3
3 2 3
1 2 3
4 3 3 
1 2 3 4
*/

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 13968kb

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: 76ms
memory: 13948kb

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