永久打开本网站的,wordpress ppt,营口建设工程信息网站,大数据分析师P2577 [ZJOI2004]午餐 $\texttt{solution}$ 想到贪心#xff1a; 吃饭慢的先打饭节约时间#xff0c; 所以先将人按吃饭时间从大到小排序。 状态#xff1a; \(f[i][j]\) 表示前 \(i\) 个人#xff0c;在 \(1号\) 窗口打饭总时间 \(j\) #xff0c;最早吃完饭的时间。 我们… P2577 [ZJOI2004]午餐 $\texttt{solution}$ 想到贪心 吃饭慢的先打饭节约时间 所以先将人按吃饭时间从大到小排序。 状态 \(f[i][j]\) 表示前 \(i\) 个人在 \(1号\) 窗口打饭总时间 \(j\) 最早吃完饭的时间。 我们可以发现 \(jk\) 等于前 \(i\) 个人打饭总和( \(sum[i]\) )\(k sum(i)-j\) 所以可以省去一维。 转移 将第 \(i\) 个人放在 \(1\) 号窗口(前提\(j \ge s[i].a\) ) \[dp[i][j] \min{(dp[i][j], \max{(dp[i-1][j-s[i].a], js[i].b)})} \]将第 \(i\) 个人放在 \(2\) 号窗口 \[dp[i][j] \min{(dp[i][j], \max{(dp[i-1][j], sum[i]-js[i].b)})} \]核心代码 bool cmp(Data x,Data y){ return x.by.b; }sort(p1,pn1,cmp);
for(int i1;in;i) sum[i]sum[i-1]p[i].a;
memset(dp,inf,sizeof(dp));
dp[0][0]0;
for(int i1;in;i)
{for(int j0;jsum[i];j){if(jp[i].a) dp[i][j]min(dp[i][j],max(dp[i-1][j-p[i].a],jp[i].b));dp[i][j]min(dp[i][j],max(dp[i-1][j],sum[i]-jp[i].b));}
}
for(int i0;isum[n];i) ansmin(ans,dp[n][i]); P1026 统计单词个数 $\texttt{solution}$ 难点 双重 \(\operatorname{DP}\) 。 字符串处理 \(\) 难以理解的题意 。 状态 设 \(sum[l][r]\) 表示从 \(i\) 到 \(j\) 的单词数 。可以直接枚举区间和单词(字符串)转移。 \(dp[i][k]\) 表示第 \(i\) 个位置分了 \(k\) 块能得到的最多的单词数 。 转移 \[dp[i][k]\max_{pk}^{pi}{\{ dp[i][k] , dp[p][k-1]sum[p1][i] \}} \]代码 bool check(int l,int r)
{string cs.substr(l,r-l1);for(int i1;it;i) if((c.find(a[i]))0) return true;return false;
}
void pre()
{for(int r1;rlen;r)for(int lr;l1;l--){sum[l][r]sum[l1][r];if(check(l,r)) sum[l][r];}
}
void solve()
{for(int i1;ik;i) dp[i][i]dp[i-1][i-1]sum[i][i];for(int i1;ilen;i) dp[i][1]sum[1][i];for(int i1;ilen;i) for(int k1;kmin(k,i-1);k) for(int pk;pi;p)dp[i][k]max(dp[i][k],dp[p][k-1]sum[p1][i]);printf(%d\n,dp[len][k]);
}
void init()
{cinwk;string c;for(int i1;iw;i) cinc,sc;lens.length(),s s;cint;for(int i1;it;i) cina[i];
} P2679 子串 $\texttt{solution}$ 状态 设 \(dp[i][j][k][0/1]\) 表示 \(A\) 的前 \(i\) 个字符和字符串 \(B\) 的前 \(j\) 个字符用了 \(k\) 个子串\(A\) 第 \(i\) 为取或不取的合法方案数。 初始化对于 \(1 \le i \le n\) \(dp[i][0][0][0] 0\) 。 转移 \[dp[i][j][k][0](dp[i-1][j][k][0]dp[i-1][j][k][1])\mod{1e97} \]\[dp[i][j][k][1](dp[i-1][j-1][k][1]dp[i-1][j-1][k-1][0]dp[i-1][j-1][k-1][1])\mod{1e97} \]代码 f[0][0][0]1;
for(int i1;in;i)
{memset(g,0,sizeof(g)),g[0][0][0]1;for(int j1;jmin(i,m);j)for(int k1;kmin(j,p);k){g[j][k][0](f[j][k][0]f[j][k][1])%mod;if(a[i]b[j]) g[j][k][1]((f[j-1][k][1]f[j-1][k-1][0])%modf[j-1][k-1][1])%mod;}memcpy(f,g,sizeof(f));
}
printf(%d\n,(f[m][p][0]f[m][p][1])%mod); P1052 过河 $\texttt{solution}$ 难点 离散化 \(len\) 的范围太大无法作为数组下标所以先离散化再 \(\operatorname{DP}\) 。两点间的距离 \(d\) 大于 \(t\) 时一定可以由 \(d\%t\) 跳过来所以最多只需要 \(td\%t\) 种距离的状态就可以表示这两个石子之间的任意距离关系。 代码 bool cmp(int x,int y){ return xy; }lenrd();
srd(),trd(),mrd();
for(int i1;im;i) a[i]rd();
a[m1]len;
sort(a1,am1,cmp);
for(int i1;im1;i)
{if(a[i]-a[i-1]t) cnt(a[i]-a[i-1])%tt;else cnta[i]-a[i-1];val[cnt]1;
}
memset(dp,inf,sizeof(dp)),dp[0]0;
for(int i1;icntt-1;i) for(int js;jt;j)if(ij) dp[i]min(dp[i],dp[i-j]val[i]);
for(int icnt;icntt-1;i) ansmin(ans,dp[i]);
printf(%d\n,ans); P5664 Emiya 家今天的饭 $\texttt{solution}$ 首先考虑列的限制必然 有且只有一列 是 不合法 的因为不可能有不同的两列数量都 超过总数的一半 。\(ans\) 总状态 \(-\) 不合法状态 计算不合法方案 计算列的不合法方案数每行选不超过一个的方案数 \(-\) 每行选不超过一个且某一列选了超过一半的方案数。可以发现每一列都是独立的可以枚举当某一列( 记为 \(cal\) )不合法时的方案再相加。 状态 先设 \(dp[i][j][k]\) 表示表示对于 \(col\) 这一列前 \(i\) 行在 \(col\) 列中选了 \(j\) 个在其他列中选了 \(k\) 个的非法方案数。令 \(sum[i]\) 为第 \(i\) 行的总和 。 转移 \[dp[i][j][k]dp[i-1][j][k] a[i][cal]\times dp[i-1][j-1][k](sum[i]-a[i][cal])\times dp[i-1][j][k-1] \]复杂度\(O(mn^3)\) 可以得到 \(84pts\) 。 考虑优化 在不合法情况的转移过程中我们并不关心 \(j\) \(k\) 的具体数值而只关心相对的大小关系。 状态 \(dp[i][j]\) 表示前 \(i\) 行当前列的数比其他列的数多了 \(j\) 个 。 转移 \[dp[i][j]dp[i-1][j]a[i][cal]\times dp[i-1][j-1](sum[i]-a[i][cal])\times dp[i-1][j1] \]复杂度\(O(mn^2)\) 复杂度在时间范围内。 统计总方案数 状态 设 \(cnt[i][j]\) 为前 \(i\) 行共选了 \(j\) 个数的方案数 。 转移 \[cnt[i][j]cnt[i-1][j]sum[i]\times cnt[i-1][j-1] \]总方案就是 \(\sum_{i1}^n {g[n][i]}\) 。 复杂度\(O(n^2)\) 可以通过这道题。 代码 for(int i1;in;i) for(int j1;jm;j)a[i][j]rd(),sum[i](sum[i]a[i][j])%mod;
for(int cal1;calm;cal)
{memset(dp,0,sizeof(dp)),dp[0][n]1;for(int i1;in;i) for(int jn-i;jni;j)dp[i][j](dp[i-1][j]dp[i-1][j-1]*a[i][cal]%moddp[i-1][j1]*((sum[i]mod-a[i][cal])%mod)%mod)%mod;for(int j1;jn;j) unok(unokdp[n][jn])%mod;
}
cnt[0][0]cnt[1][0]1;
for(int i1;in;i,cnt[i][0]cnt[i-1][0]) for(int j1;jn;j)cnt[i][j](cnt[i-1][j]sum[i]*cnt[i-1][j-1]%mod)%mod;
for(int i1;in;i) ans(anscnt[n][i])%mod;
printf(%lld\n,(ansmod-unok)%mod); P2258 子矩阵 $\texttt{solution}$ 题意 在 \(n\times m\) 的矩阵中选取 \(r\times c\) 的子矩阵(可以跳行 \(/\) 跳列间隔选取)使子矩阵相邻两元素的差之和最小 。 题解 算法枚举 \( \operatorname{DP}\) 。 考虑到 \(n,m\) 比较小所以先枚举选出那些行 这里的复杂度为 \(O(C_n^r)\) 。 之后考虑 \(\operatorname{DP}\) 选取列 1. 预处理 处理出单独选一列这 \(r\) 行上下之间的差之和( \(lie[i]\) ) 。 再处理如果选了第 \(i\) 列和第 \(j\) 列这两列横着的 \(r\) 行元素的差值之和( \(hang[i][j]\) ) 。 2. \(\operatorname{DP}\) 设 \(dp[i][j]\) 表示在前 \(i\) 行中选了 \(j\) 行的最小差值之和 。 转移 当 \(j1\) 时\(dp[i][j]\) 为仅选第 \(i\) 列的差值之和 。 其他情况可以枚举 \(k[j-1,i-1]\) 考虑子矩阵的第 \(j-1\) 选择为 \(k\) 的情况下的代价是多少并取 \(\min\) 转移。 代码 int ansinf;
void solve()
{for(int i1;im;i) lie[i]0;for(int i1;im;i) for(int ji1;jm;j) hang[i][j]0;for(int i1;im;i) for(int j2;jr;j) lie[i]abs(a[ch[j]][i]-a[ch[j-1]][i]);for(int i1;im;i) for(int ji1;jm;j) for(int k1;kr;k)hang[i][j]abs(a[ch[k]][j]-a[ch[k]][i]);for(int i1;im;i) for(int j1,Limitmin(i,c);jLimit;j){if(j1) dp[i][j]lie[i];else{dp[i][j]inf;for(int kj-1;ki;k) dp[i][j]min(dp[i][j],dp[k][j-1]lie[i]hang[k][i]);}}for(int ic;im;i) ansmin(ans,dp[i][c]);
}
void dfs(int Left,int st)
{if(!Left){solve();return;}if(stn) return;for(int ist;in-Left1;i) ch[r-Left1]i,dfs(Left-1,i1);
}dfs(r,1);
printf(%d\n,ans); P6064 [USACO05JAN]Naptime G $\texttt{solution}$ 算法线性 \(\operatorname{DP}\) 列出基础转移方程 先不考虑第 \(n\) 个小时与次日第 \(1\) 个小时连续 。 设 \(dp[i][j][0/1]\) 表示在第 \(i\) 个小时已经在床上躺了 \(j\) 个小时\(0\) 表示这个小时没在床上\(1\) 表示这个小时正躺在床上 。 转移方程( 初始值 \(dp[1][0][0]dp[1][1][1]0\) 其他为 \(-\inf\) ) \[\begin{cases}dp[i][j][0]\max{\{dp[i-1][j][0],dp[i-1][j][1]\}}\\dp[i][j][1]\max{\{dp[i-1][j-1][0],dp[i-1][j-1][1]u[i]\}}\end{cases} \]目标\(\min{\{dp[n][b][0],dp[n][b][1]\}}\) 。 完善转移方程 考虑第 \(n\) 个小时与次日第 \(1\) 个小时连续 即强制第第 \(n\) 个小时睡觉 。 初始值\(dp[1][0][0]0,dp[1][1][1]u[1]\) 其他为 \(-\inf\) 。 目标\(dp[n][m][1]\) 。 最终答案为两种情况的较大值。 代码 #define inf 0x7f7f7f7f
#define Maxn 3835
int n,b,ans,a[Maxn],dp[Maxn][Maxn][2];// 一下代码片段插入在 main 函数中
nrd(),brd();
for(int i1;in;i) a[i]rd();
memset(dp,-inf,sizeof(dp)),dp[1][1][1]dp[1][0][0]0;
for(int i2;in;i)
{dp[i][0][0]dp[i-1][0][0];for(int j1;jb;j){dp[i][j][0]max(dp[i-1][j][1],dp[i-1][j][0]);dp[i][j][1]max(dp[i-1][j-1][0],dp[i-1][j-1][1]a[i]);}
}
ansmax(dp[n][b][0],dp[n][b][1]);
memset(dp,-inf,sizeof(dp)),dp[1][1][1]a[1],dp[1][0][0]0;
for(int i2;in;i)
{dp[i][0][0]dp[i-1][0][0];for(int j1;jb;j){dp[i][j][0]max(dp[i-1][j][1],dp[i-1][j][0]);dp[i][j][1]max(dp[i-1][j-1][0],dp[i-1][j-1][1]a[i]);}
}
ansmax(ans,dp[n][b][1]);
printf(%d\n,ans); P1043 数字游戏 $\texttt{solution}$ 算法环形 \(\operatorname{DP}\) 。 方法 破环成连把环变为两倍统计答案的时候把答案扫一遍。 用 \(dp[l][r][p]\) 表示把 \(l\) 至 \(r\) 这一个区间分为 \(p\) 段的最小 \(/\) 最大代价 。 代码 int ansmininf,ansmax;
int MAX[Maxn][Maxn][Maxm],MIN[Maxn][Maxn][Maxm];
inline int mod(int x) { return ((x%10)10)%10; } // 保证是正数nrd(),mrd();
for(int i1;in;i) a[i]a[in]rd();
for(int i1;in*2;i) sum[i]sum[i-1]a[i];
memset(MIN,inf,sizeof(MIN)); // ↓ 初始化一些状态
for(int l1;ln*2;l) for(int rl;rn*2;r) MAX[l][r][1]MIN[l][r][1]mod(sum[r]-sum[l-1]);
for(int p2;pm;p) for(int l1;lp-1n*2;l) for(int rlp-1;rn*2;r) for(int klp-2;kr;k)
{MAX[l][r][p]max(MAX[l][r][p],MAX[l][k][p-1]*mod(sum[r]-sum[k]));MIN[l][r][p]min(MIN[l][r][p],MIN[l][k][p-1]*mod(sum[r]-sum[k]));
} // k 是枚举转移点
for(int i1;in;i) ansminmin(ansmin,MIN[i][in-1][m]),ansmaxmax(ansmax,MAX[i][in-1][m]); // 扫一遍答案
printf(%d\n%d\n,ansmin,ansmax); P2331 [SCOI2005]最大子矩阵 $\texttt{solution}$ 题意 这里有一个 \(n\times m\) 的矩阵请你选出其中 \(k\) 个子矩阵使得这个 \(k\) 个子矩阵分值之和最大。 注意选出的 \(k\) 个子矩阵不能相互重叠。 其中\(1\le n\le 100,1\le m\le 2,1\le k\le 10\) 题解 注意到 \(m\) 比较小分为几类 当 \(m1\) 时是普通的最大连续字段和只不过是 \(k\) 个 设 \(dp[i][j]\) 表示前 \(i\) 个数中取出 \(j\) 个矩形的最大和 转移 选 \[dp[i][j]\max_{l1}^{li}{\{dp[l][j-1]s[i]-s[l-1]\}} \]不选 \[dp[i][j]\max(dp[i][j],dp[i-1][j]) \]复杂度 \(O(n^2\times k)\) 当 \(m2\) 时设 \(f[i][j][k]\) 表示第一列选到第 \(i\) 个数第二列选到第 \(j\) 个数时总共 \(k\) 个子矩形的答案 转移有 \(4\) 种情况 当这一位什么都不做的时候 \[f[i][j][k]\max(f[i-1][j][k],f[i][j-1][k]) \]当仅选取第一列的某段区间时 \[f[i][j][k]\max_{l1}^{li}{\{f[l][j][k-1]sum[i][1]-sum[l-1][1]\}} \]当仅选取第二列的某段区间时 \[f[i][j][k]\max_{l1}^{lj}{\{f[i][l][k-1]sum[j][2]-sum[l-1][2]\}} \]当 \(ij\) 时可以选取两列一起的 \[f[i][j][k]\max_{l1}^{l \min(i,j)}{\{f[l][l][k]sum[i][1]sum[i][2]-sum[l-1][1]-sum[l-1][2]\}} \]最后所有情况取 \(\max\) 。 复杂度 \(O(n^3\times k)\) CF1174E Ehab and the Expected GCD Problem $\texttt{solution}$ 首先考虑在权值最大时第一个数一定为 \(2^x2^y\) 且 \(y\le 1\) 。 再分析往下填的数考虑 \(dp[i][j][k]\) 表示填到第 \(i\) 个前缀 \(\gcd\) 为 \(2^j3^k\) 时的方案数。 可以填 \(2^j3^k,2^{j-1}3^k,2^j3^{k-1}\) 的倍数分别讨论。 CF149D Coloring Brackets $\texttt{solution}$ (需要想到区间 \(\text{DP}\) ) \(dp(l,r,i,j)\) 表示区间 \([l,r]\) 中左端点颜色为 \(i\) 右端点颜色为 \(j\) 的涂色方案数。 分为三类情况 \(l1r\) 直接赋值。\(match(l)r\) 由 \(dp(l1,r-1,,)\) 转移而来。\(match(l)!r\) 由 \(dp(l,match(l),,)\times dp(match(l)1,r,,)\) 转移而来。 由于这一题的局部最优解与全局最优解之间没有直接方便的转移方式所以使用递归的方式求出 \(\text{DP}\) 值。 P3592 [POI2015]MYJ $\texttt{solution}$ 因为 \(n\le 50,m\le 300\)所以考虑一个 \(O(n^3)\) 的算法这样容易想到区间 \(\text{dp}\)。 把付的钱离散化 \(cnt(i,j)\) \([l,r]\) 中在 \(i\) 位置填颜色 \(j\) 的消费人数 \(dp(l,r,k)\) 在 \([l,r]\) 中最少的钱为 \(k\) 时的最大获得钱数 在转移时与 \(dp(l,r,k1)\) 取 \(\max\) 因为 \(k\) 比 \(k1\) 少 记下这个状态最优时【最少的钱的位置】与【最少的钱的钱的多少】 CF840C On the Bench $\texttt{solution}$ 把 \(p\) 除去所有平方因子转化为相邻的 \(p\) 互不相同。 想象把数一个一个塞到原序列中。 \(dp(i,j,k)\) 放了 \(i\) 个\(j\) 个相同且相邻\(k\) 个与第 \(i\) 个数相同且相邻 为什么想到要这么假设呢 为了让数字相同的一起处理把 \(p\) 排好序并且在颜色变化时记得更新~ 起始状态 \(dp(0,0,0)\) 目标 \(dp(n,0,0)\) 处理出一个数和之前多少个数相同 ( \(pre\) ) 若塞入后和左/右其一相同 \[dp[i-1][j][k]\times(prepre-k[可以塞的位置])-dp[i][j1][k1] \]若塞入后与左右都不同但左右相同 \[dp[i-1][j][k]\times(j-k[可以塞的位置])-dp[i][j-1][k] \]若塞入后与左右都不同且左右不同 \[p[i-1][j][k]\times(i[总位置数]-(prepre-k)[情况 1 ]-(j-pre)[情况 2 ])-dp[i][j][k] \] CF830D Singer House $\texttt{solution}$ 考虑把深度一个一个累加去考虑怎样从上一个阶段转移到这一个阶段。 假设增加了一层不妨假设用一个新的根节点合并两颗深度为 \(n-1\) 的子树(明显这样更好维护呀) 设此时的答案为 \(f_n\) 。 一个思路是考虑这条路径是否经过根节点那么有几种情况 这条路径只包含根节点这条路径从下面某棵子树内一条路径连上来再连接下去 乍一看似乎能做但是我们会发现从一棵子树中连上来的路径可能会连回同一棵子树那么如果我们要算\(f_n\) 就必须算出从深度为 \(n-1\) 的子树内选择两条不相交的路径的方案数 \(g_{n-1}\) 。 你可能会想继续讨论 \(g_n\) 的方案数但是你会发现你要算 \(g_n\) 还得算深度为 \(n-1\) 的树种选三条不相交路径的方案数…… 既然如此我们观察一下数据范围 不妨多设一维状态 令 \(f_{n,k}\) 代表在深度为 \(n\) 的树中选择 \(k\) 条不相交路径的方案数。 看上去似乎变难了毕竟原题只让我们求一条路径的方案数。 但是我们发现这个“加强”版本似乎更好做了因为转移变得十分简单 \[f_{n,k}\sum_{ijk-1}f_{n-1,i}\times f_{n-1,j} \]\[\sum_{ijk}f_{n-1,i}\times f_{n-1,j} \]\[\sum_{ijk}f_{n-1,i}\times f_{n-1,j}\times (2k) \]\[\sum_{ijk1}f_{n-1,i}\times f_{n-1,j}\times (k1)\times k \]这四种情况分别是根节点单独形成一条链、根节点不属于任何一条链、根节点与左右子树内某条链连在一起(分从链的尾端连上来和连到链的开头两种情况)、还有根节点从某条链上连上再连到另一条链上去。 参考
