ap325第二天筆記

ap325第二天筆記

一月 09, 2025

遞迴

  • 支點切割

https://zerojudge.tw/ShowProblem?problemid=f638
寫了兩個小時還是錯的決定先休息，放這裡之後寫，寫了兩個小時發現我沒看完題目
放一個正解網址https://sites.google.com/view/zsgititit/home/jin-jiec-cheng-shi-she-ji/apcs201802%E7%AC%AC3%E9%A1%8C%E6%94%AF%E9%BB%9E%E5%88%87%E5%89%B2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
LL s[500100]={};
int T=0;
/*
5 1
1 2 3 4 100
*/
LL cut(int left,int right,int boundd){
    if((right-left)<=1 ||(boundd)>=T){
        return 0;
    }

    int k=left+1;
    LL low=LLONG_MAX;
    //int low=abs((s[left]-s[left-1])-(s[right]-s[left+1]));//差值
    //cout<<low<<" low \n";
    for(int i=left+1;i<=right-1;i++){
        if(abs((s[i-1]-s[left-1])-(s[right]-s[i]))<low){
            k=i;
            low=abs((s[i-1]-s[left-1])-(s[right]-s[i]));
            //cout<<low<<" low "<<k<<" k \n";
        }

    }
    boundd++;
    return s[k]-s[k-1]+cut(left,k-1,boundd)+cut(k+1,right,boundd);

}


int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    cin>>T;
    LL g;
    s[0]=0;
    for(int i=1;i<=n;i++){
        cin>>g;
        s[i]=g+s[i-1];
    }
    /*for(int i=0;i<=n;i++){
        cout<<s[i]<<' ';
    }
    cout<<'\n';*/
    cout<<cut(1,n,0);
    return 0;
}