• ClueOJ
  • Trang chủ
  • Danh sách bài
  • Các bài nộp
  • Các kỳ thi
  • Thư viện đề thi
  • Thành viên
    >
    • Tổ chức
  • Thông tin
    >
    • Máy chấm
    • Discord
    • blog
  • Đăng ký tổ chức
    >
    • Offline Contest
    • Viết lại đề bài
VI EN Đăng nhập  hoặc  Đăng ký

quangthanh

  • Thông tin
  • Thống kê
  • Blog
  • Chuỗi

Số bài đã giải: 83
Hạng điểm: #196
Tổng điểm: 1802,23
Đóng góp: 0
Chuỗi luyện tập
0
ngày liên tiếp
Kỷ lục 3 ngày

Xem các bài nộp

Thông tin

https://oj.clue.edu.vn/problem/dhbb26seq https://oj.clue.edu.vn/problem/tqhsg26d -> nâng lên n = 2e5 https://oj.clue.edu.vn/problem/dntst24varr https://oj.clue.edu.vn/problem/hnhsg25e https://oj.clue.edu.vn/problem/hsgso26recurio https://oj.clue.edu.vn/problem/voi26pine 50b30 50b35 50b40 50b45 50b50 50b55 50b60

include <bits/stdc++.h>

using namespace std;

define ll long long

const ll N = 2e5 + 5;

ll n,k,t[N]; namespace sub1 { ll f[5005][5005],res = 1e18; void solve() { for(ll i = 1; i <= n; i ++) { for(ll j = 1; j <= n; j++) { f[i][j] = 1e18; } } for(ll i =1 ; i <= n; i ++) { for(ll j = 1 ; j <= i; j++) { ll chiphi = t[i] + 1 - t[j] + 1; for(ll x = 0; x <= k - 1; x ++) { if(f[j - 1][x + 1] != 1e18) f[i][x] = min(f[i][x],f[j - 1][x + 1] + chiphi); } } } fl(i,1,k) { res = min(res,f[n][i]); } cout << res; } } namespace sub2 { ll f[5005][5005],g[5005],res = 1e18; void solve() { for(ll i = 1; i <= n; i ++) { for(ll j = 1; j <= k; j++) { f[i][j] = 1e18; } } for(ll i =1; i <= k; i++) { g[i] = 1e18; f[0][i] = 1e18; } for(ll i =1 ; i <= n; i++) { for(ll x = 1; x <= k; x++) { g[x] = min(g[x],f[i - 1][x] - t[i]); } for(ll x = 0; x <= k - 1; x ++) { if(g[x + 1] != 1e18) { f[i][x] = min(f[i][x],g[x + 1] + t[i] + 1); } } } for(ll i = 0; i<= k; i++) { res = min(res,f[n][i]); } cout << res; } } main() { cin.tie(0)->syncwithstdio(0); cin >> n >> k; for(ll i = 1; i <= n; i++) { cin >> t[i]; } if(n <= 400) sub2::solve(); else if(n <= 5000) sub3::solve(); }

Huy hiệu

Người dùng này không có huy hiệu nào.

«    »
CN
T2
T3
T4
T5
T6
T7
Ít
Nhiều

dựa trên nền tảng DMOJ | follow us on Github, Discord and Facebook