P2157-[SDOI2009]学校食堂

迈不过友情╰ 2023-06-01 08:53 22阅读 0赞

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 typedef double db;
     5 #define INF 0x3f3f3f3f
     6 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     7 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     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 int T[1003];
    24 int B[1003];
    25 int dp[1003][1<<8][18];
    26 int main()
    27 {
    28     int TT = read();
    29     while(TT--)
    30     {
    31         int n = read();
    32         _for(i,1,n+1)
    33         T[i] = read(), B[i] = read();
    34 
    35         memset(dp,INF,sizeof(dp));
    36         dp[1][0][7] = 0;
    37         _for(i,1,n+1)
    38         _for(j,0,(1<<8))
    39         _for(k,-8,8)
    40         if(dp[i][j][k+8]!=INF)
    41             if(j&0x1)
    42                 dp[i+1][j>>1][k+7] = min(dp[i+1][j>>1][k+7],dp[i][j][k+8]);
    43             else
    44             {
    45                 int r = INF;
    46                 _for(h,0,8)
    47                 if(!((j>>h)&0x1) && i+h<=r)
    48                 {
    49                     r = min(r,i+h+B[i+h]);
    50                     if(!(i+k))
    51                         dp[i][j|(1<<h)][h+8] = min(dp[i][j|(1<<h)][h+8],
    52                                                    dp[i][j][k+8]);
    53                     else
    54                         dp[i][j|(1<<h)][h+8] = min(dp[i][j|(1<<h)][h+8],
    55                                                    dp[i][j][k+8]+(T[i+k]^T[i+h]));
    56                 }
    57             }
    58         int res = INF;
    59         _for(k,0,9)
    60         res = min(res,dp[n+1][0][k]);
    61         write(res);
    62         printf("\n");
    63     }
    64     return 0;
    65 }

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