当前位置：网站首页>2020.4.12 byte written test questions B DP D monotone stack

2020.4.12 byte written test questions B DP D monotone stack

2022-07-02 15:49:00 【ccsu_ deer】

A Simple exchange
Water problem ..

B-- Folding stick

The solution comes from friends
f[i][j]: The first i The maximum value of wooden sticks is j The minimum number of disassembly to make the previous conditions meet
Greedy to get a minimum value of this kind of split stick X And times S
f[i][j]=max(f[i-1][k]+s) k<=x
In fact, that is Every stick a[i] The maximum enumeration value is len ( On the far right is len) And the leftmost : a[i]%len Calculate the minimum disassembly ：s=a[i]/len+((a[i]%len==0)?0:1)-1
According to each position len The leftmost number is either a[i]%len Or len How to calculate What about the legal maximum on the far left ？pos+1 Number Average a[i] Just fine k=a[i]/(pos+1)

       
        #include<bits/stdc++.h>
        
#define LL long long
        
using namespace std;
        

        
LL a[3005], f[3005][3005];
        

        
int main() {
        

        
    int n; scanf("%d", &n);
        
    for(int i=1; i<=n; i++){
        
        scanf("%lld", &a[i]);
        
    }
        
    memset(f, 7, sizeof(f));
        
    for(int i=0; i<3005; i++) f[0][i]=0;
        

        
    for(int i=1; i<=n; i++){
        
        for(int len=1; len<3005; len++){
        
            if(len>a[i]){
        
                f[i][len]=f[i][len-1];
        
                continue;
        
            }
        
            LL pos=a[i]/len+((a[i]%len==0)?0:1)-1;// according to mi len len len  Number of cuts pos
        
            LL mi=((a[i]%len==0)?len:(a[i]%len));
        
            //pos*len+mi==a[i]
        
            LL x=(pos*len+mi)/(pos+1);// cut pos Dao you pos+1 A place ,a[i] To give evenly to pos+1 A position is the maximum legal value x
        

        
            //printf("mi:%lld x:%lld\n",mi,x);
        
            f[i][len]=f[i-1][x]+pos;
        
            f[i][len]=min(f[i][len], f[i][len-1]);
        
            //cout<<i<<" "<<len<<" "<<f[i][len]<<endl;
        
        }
        
    }
        
    LL ans=1<<30;
        
    for(int i=1; i<=a[n]; i++){
        
        ans=min(ans, f[n][i]);
        
    }
        
    printf("%lld\n", ans);
        

        
    return 0;
        
}
        
/*
        
5
        
3 5 13 9 12
        
ans:1
        

        
5
        
5 4 3 2 1
        
ans:
        
*/
       
       
        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.

C-- Coupon
Yes a Sort ,b[i] stay a Just score two points .

D-- Stand tall Look far
Classic monotonous stack question

       
        #include<bits/stdc++.h>
        
#define rep(i,a,b) for(int i=a;i<=(b);++i)
        
#define mem(a,x) memset(a,x,sizeof(a))
        
#define pb push_back
        
#define pi pair<int, int>
        
#define mk make_pair
        
using namespace std;
        
typedef long long ll;
        
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
        
const int N=1e6+10;
        
int a[N],ans[N],n,m,l[N],r[N];
        
int main()
        
{
        
   int _;cin>>_;while(_--)
        
   {
        
       scanf("%d",&n);
        
       rep(i,1,n) scanf("%d",&a[i]);
        
       stack<int>sta;
        
       rep(i,1,n) l[i]=r[i]=i;
        
       for(int i=1;i<=n;++i){
        
            if(sta.size()==0) sta.push(i);
        
            else{
        
                while(sta.size()&&a[i]>=a[sta.top()]) {
        
                    sta.pop();
        
                }
        
                if(sta.size()) l[i]=sta.top()+1;
        
                else l[i]=1;
        
                sta.push(i);
        
            }
        
       }
        
       while(sta.size()) sta.pop();
        

        
       for(int i=n;i;--i){
        
            if(sta.size()==0) sta.push(i);
        
            else{
        
                while(sta.size()&&a[i]>=a[sta.top()]) {
        
                    sta.pop();
        
                }
        
                if(sta.size()) {
        
                    r[i]=sta.top()-1;
        

        
                }
        
                else r[i]=n;
        

        
                sta.push(i);
        
            }
        
       }
        
       rep(i,1,n)
        
       {
        
           printf("%d ",r[i]-l[i]);
        
       }
        
       puts("");
        

        

        
   }
        
}
       
       
        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.
        53.
        54.
        55.
        56.