Submission #881072

#	Time	Username	Problem	Language	Result	Execution time	Memory
881072		alexdd	Skyline (IZhO11_skyline)	C++17	0 / 100	4 ms	12772 KiB

skyline

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n;
int dp[315][205][205];
int h[315];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(int i=1;i<=n+2;i++)
        for(int u=0;u<=200;u++)
            for(int j=0;j<=200;j++)
                dp[i][u][j]=INF;
    dp[2][h[1]][h[2]]=0;
    for(int i=2;i<=n+1;i++)
    {
        for(int j=0;j<=200;j++)
        {
            for(int k=0;k<=200;k++)
            {
                int p=j,u=k;
                if(dp[i][p][u]==INF)
                    continue;
                int nxt = h[i+1];
                int cnt3 = min({p,u,nxt});
                p -= cnt3;
                u -= cnt3;
                nxt -= cnt3;
                int cnt2 = min(p,u);
                p -= cnt2;
                u -= cnt2;
                int cnt1 = p;
                p -= cnt1;
                dp[i+1][u][nxt] = min(dp[i+1][u][nxt], dp[i][j][k] + cnt1*3 + cnt2*5 + cnt3*7);

                p=j;
                u=k;
                nxt=h[i+1];
                cnt2 = min(p,u);
                p -= cnt2;
                u -= cnt2;
                cnt1 = p;
                p -= cnt1;
                dp[i+1][u][nxt] = min(dp[i+1][u][nxt], dp[i][j][k] + cnt1*3 + cnt2*5);

                p=j;
                u=k;
                cnt1 = p;
                p -= cnt1;
                dp[i+1][u][nxt] = min(dp[i+1][u][nxt], dp[i][j][k] + cnt1*3);
            }
        }
    }
    cout<<min({dp[n][0][0],dp[n+1][0][0],dp[n+2][0][0]});
    return 0;
}
/**

dp[i][p][u] = costul minim pentru a construi toate cladirile 1..i-2, iar cladirea i-1 sa mai aiba nevoie de p inaltime, iar cladirea i de u inaltime
dp[i+1][

dp[i][p][u] = min(dp[i-1][])

*/

• Subtask 1: 0 / 100