P1220-关路灯

女爷i 2023-06-01 08:52 100阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define MOD 1000000007
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 struct lamp
    24 {
    25     int pos;
    26     int power;
    27 };
    28 int n,c;
    29 lamp a[53];
    30 int dp[53][53][2];
    31 int sum[53][53];
    32 int main()
    33 {
    34     n = read(), c = read();
    35     _for(i,1,n+1)
    36         a[i].pos = read(),a[i].power = read();
    37 
    38     _for(i,1,n+1)
    39     {
    40         sum[i][i] = a[i].power;
    41         _for(j,i+1,n+1)
    42             sum[i][j] = sum[i][j-1]+a[j].power;
    43     }
    44 
    45     memset(dp,0x3f,sizeof(dp));
    46     if(c>=2)
    47         dp[c-1][c][0] = (a[c].pos-a[c-1].pos)*(sum[1][c-1]+sum[c+1][n]);
    48     if(c<=n-1)
    49         dp[c][c+1][1] = (a[c+1].pos-a[c].pos)*(sum[1][c-1]+sum[c+1][n]);
    50 
    51     _for(len,3,n+1)
    52         _for(l,1,n-len+2)
    53         {
    54             int r = l+len-1;
    55             dp[l][r][0] = min(dp[l+1][r][0]+(a[l+1].pos-a[l].pos)*(sum[1][l]+sum[r+1][n])
    56             ,dp[l+1][r][1]+(a[r].pos-a[l].pos)*(sum[1][l]+sum[r+1][n]));
    57             dp[l][r][1] = min(dp[l][r-1][0]+(a[r].pos-a[l].pos)*(sum[1][l-1]+sum[r][n])
    58             ,dp[l][r-1][1]+(a[r].pos-a[r-1].pos)*(sum[1][l-1]+sum[r][n]));
    59         }
    60     write(min(dp[1][n][0],dp[1][n][1]));
    61     return 0;
    62 }

转载于:https://www.cnblogs.com/Asurudo/p/11411863.html