CF771E Bear and Rectangle Strips

一、题目

点此看题

二、解法

首先设计出暴力 \(dp\)，设 \(dp[i][j]\) 表示第一行考虑到 \(i\)，第二行考虑到 \(j\) 的最大得分，先写转移：

  • 扩展第一行，可以无得分让 \(i+1\)；可以选从 \(i+1\) 开始的和为 \(0\) 的段（选右端点最小的）
  • 扩展第二行，可以无得分让 \(j+1\)，可以选从 \(j+1\) 开始的和为 \(0\) 的段。
  • \(i=j\) 时，同时扩展两行，选一个 \(i+1\) 开始的何为 \(0\) 的矩阵。

优化的关键是只有 \(i=j\) 时两行的转移才有交叉，否则两行的转移是相对独立的。一个至关重要的 \(\tt observation\) 是当 \(i\not=j\) 时，我们只用扩展较小的那一行（指 \(i,j\) 比较出来较小）。因为如果不考虑第三种转移那么先扩展哪一行都是没关系的，否则扩展较小的一行就更有利于考虑第三种转移。

那么我们以 \(dp[i][i]\) 为转移主体，也就是考虑两行前 \(i\) 列的最大得分，对于 \(i\not=j\) 的扩展，我们只需要找到最小的 \(j\) 使得 \(dp[i][j]=dp[i][i]+1\)（或者 \(dp[j][i]=dp[i][i]+1\)），因为如果 \(dp[i][j]>dp[i][i]+1\) 那么说明某一行扩展多了，不符合上述结论所以自然不用考虑。

转移的时候维护那个 \(j\) 即可，时间复杂度 \(O(n)\)，算上预处理的 \(\tt map\) 时间复杂度 \(O(n\log n)\)

三、总结

考虑有效转移是优化的重要方法，也就是如果某一种转移的作用会在以后被解决那么我们就不用考虑它。

#include 
#include 
#include 
#include 
using namespace std;
const int M = 300005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[2][M],nx[3][M],s[3],dp[M];map mp[3];
struct node
{
	int x,y,c;
};vector vc[M];
void add(int x,int y,int c)
{
	dp[max(x,y)]=max(dp[max(x,y)],c);
	vc[min(x,y)].push_back(node{x,y,c});
}
void extend(int x,int y,int c)
{
	if(x
DP

相关

DP决策优化小结

dp专题练习

腾讯云搭建个人博客wordpress

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

Java高并发，ThreadPoolExecutor线程池技术

sqlserver with(NOLOCK) 或 with(READPAST）

单调队列优化DP历险记

CS5262设计DP转HDMI 4K60HZ +VGA 1080P方案芯片

「NOI2020」命运（树形DP+线段树合并）

线程池ThreadPool知识碎片和使用经验速记

阿里面试官常问的TCP和UDP，你真的弄懂了吗？

标签