临沂恒商做网站,输入姓名查询个人征信,整形网站开发,公众号网页制作模板P2157 [SDOI2009]学校食堂
题意#xff1a;
小F 的学校在城市的一个偏僻角落#xff0c;所有学生都只好在学校吃饭。学校有一个食堂#xff0c;虽然简陋#xff0c;但食堂大厨总能做出让同学们满意的菜肴。当然#xff0c;不同的人口味也不一定相同#xff0c;但每个人…P2157 [SDOI2009]学校食堂
题意
小F 的学校在城市的一个偏僻角落所有学生都只好在学校吃饭。学校有一个食堂虽然简陋但食堂大厨总能做出让同学们满意的菜肴。当然不同的人口味也不一定相同但每个人的口味都可以用一个非负整数表示。 由于人手不够食堂每次只能为一个人做菜。做每道菜所需的时间是和前一道菜有关的若前一道菜的对应的口味是a这一道为b则做这道菜所需的时间为a or b-a and b而做第一道菜是不需要计算时间的。其中or 和and 表示整数逐位或运算及逐位与运算C语言中对应的运算符为“|”和“”。
学生数目相对于这个学校还是比较多的吃饭做菜往往就会花去不少时间。因此学校食堂偶尔会不按照大家的排队顺序做菜以缩短总的进餐时间。
虽然同学们能够理解学校食堂的这种做法不过每个同学还是有一定容忍度的。也就是说队伍中的第i 个同学最多允许紧跟他身后的Bi 个人先拿到饭菜。一旦在此之后的任意同学比当前同学先拿到饭当前同学将会十分愤怒。因此食堂做菜还得照顾到同学们的情绪。 现在小F 想知道在满足所有人的容忍度这一前提下自己的学校食堂做完这些菜最少需要多少时间。
题解
状压dp不难看出但是不会写 每个人既要考虑前面的人也要顾虑后面的情况 如何确定动态转移方程
我们可以认为已经处理了前i-1个情况正在处理第i个边界情况是吃没吃饭我们需要一维变量来表示i以及i后7的个人(因为i最多只能影响之后7个人)是否吃饭由于做饭时间与上一个吃饭的人有关我们还需要一维变量来存储上一个拿到饭菜的人相对于i的位置kk属于[-8,7]当k0时表示其本身
综上我们设f[i][st][k]表示前i-1给人已经吃完了i以及i后面七个人的吃饭状态是st上一次吃饭的人的位置与i的偏移是k的最短时间 例如:st(00000011)(2进制下),表示第i个和第i1个吃了其他没吃 f初始化为正无穷初始状态为 f[1][0][7] 0; 为什么f[1][0][7]为初始状态我认为k7表示第0位而我们一上来就要更新第1个人所以需要第0个人的状态。
现在我们开始更新状态 如果第i个人吃饭了那我们可以考虑转移到第i1个人即j11(也就是j的第一位是1)此时i后面7个人的吃饭顺序就不会再受到 i的影响了因为他们不可能插队到i的前面。此时转移为 f[i1][j1][k-1]min(f[i][j1][k-1],f[i][j][k]) j1是因为j是相对于当前选定对象的偏移量对于i来说是j那对于第i1个人j就要左移一位k也同理
如果第i个人没吃饭没办法转移到i1(因为i1之前的人还没吃完饭)。此时我们需要从i以及i之后的7位中选出一个人来打饭也就是枚举l从0到7此时转移方程为 f[i][j | (1 l)][l 8] min(f[i][j | (1 l)][l 8], f[i][j][k 8] Time(a[i k].t, a[i l].t)); Time是计算做饭时间,ik是上一个打饭的人il是当前要打饭的人当然如果il是第一个打饭的人Time就是0否则就是题目所说的计算值 注意每个人都有自己的忍耐范围也就是并不是所有人都能接收自己后面7个人所有我们要对于每个人如果超出了忍耐范围我们就不考虑这个人。
代码
// Problem: P2157 [SDOI2009]学校食堂
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2157
// Memory Limit: 125 MB
// Time Limit: 800 ms
// Data:2021-08-12 13:00:56
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
int f[1004][1 9][20];
struct node
{int t, b;
} a[1030];
int base 8; //偏移量
int Time(int x, int y)
{return (x | y) - (x y);
}
int main()
{//rd_test();int t;read(t);while (t--) {int n;read(n);for (int i 1; i n; i) {read(a[i].t);read(a[i].b);}memset(f, INF_int, sizeof(f));f[1][0][7] 0; //?/*f[i1][j1][k-1]min(f[i1][j1][k-1],f[i][j][k]);//ik是上一次打饭的人ih是枚举本次打饭的人f[i][j|(1h)][h]min(f[i][j|(1h)][h],f[i][j][k]Time(ik,ih));*/for (int i 1; i n; i) { //对于第i个人已经吃饭for (int j 0; j (1 8); j) { //从自己开始往后8个人的状态for (int k -8; k 7; k) { //上一次吃饭的人距离i的位置if (f[i][j][k 8] ! INF_int) {if (j 1) { //j的第一位是1说明i本身吃饭了f[i 1][j 1][(k base) - 1] min(f[i 1][j 1][(k base) - 1], f[i][j][k base]);}else { //如果第i个还未吃饭枚举它后面的人int lim INF_int;for (int l 0; l 8; l) {if (!(j (1 l))) //如果第l个人吃饭了{if (i l lim)break;lim min(lim, i l a[i l].b);if (i k) //不是第一个吃饭的{f[i][j | (1 l)][l base] min(f[i][j | (1 l)][l base], f[i][j][k base] Time(a[i k].t, a[i l].t));}else //第一个吃饭的{f[i][j | (1 l)][l base] min(f[i][j | (1 l)][l base], f[i][j][k base] 0);}}}}}}}}int res INF_int;for (int k 0; k 8; k) {res min(res, f[n 1][0][k]);}printf(%d\n, res);}//Time_test();
}
