课程好多啊，准备熬夜肝完...
加油！拿下PAT*这一次！
2022-02-21
1023 The Best Polygon
首先题目给我们的一定是一个凸多边形吧，
我们首先获得这些点中的较为平均的点，按照这个平均点进行极角序排序，然后走dp
dp[i][j][k]表示起始点为i，终点为j，多边形的个数时k的最大面积
那么dp[i][j][k] = max(dp[i][l][k - 1] + Area(i,j,l))其中i ~ l中的点数需要大于k - 1,Area指的是由i,j,l组成的三角形面积
AC代码：
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 3e2 + 7;
struct point{
double x,y;
int idx;
point(double x = 0,double y = 0):x(x),y(y){}
}a[MAXN];
double Mx,My;
double cross(point a,point b)
{return a.x * b.y - a.y * b.x;}
bool cmpp(point a,point b)
{
// OA , OB 向量
double oax = a.x - Mx;
double oay = a.y - My;
double obx = b.x - Mx;
double oby = b.y - My;
return atan2(oay,oax) < atan2(oby, obx);
}
bool cmp(point a,point b)
{return cross(point(a.x - Mx,a.y - My),point(b.x - Mx,b.y - My)) < 0;}
double dp[MAXN][MAXN][15];
int pre[MAXN][MAXN][15];
double Area(point a,point b,point c)
{return fabs(cross(point(a.x - b.x,a.y - b.y),point(c.x - b.x,c.y - b.y))) / 2.0;}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;++i)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
Mx += a[i].x;
My += a[i].y;
a[i].idx = i;
}
Mx /= n;
My /= n;
sort(a + 1,a + n + 1,cmp);
for(int k = 3;k <= m;++k)
{
for(int i = 1;i + k - 1 <= n;++i)
{//枚举起点
for(int j = i + k - 1;j <= n;++j)
{
for(int l = i + k - 2;l <= j - 1;++l)
{
double now = Area(a[i],a[j],a[l]) + dp[i][l][k - 1];
if(now > dp[i][j][k])
{
dp[i][j][k] = now;
pre[i][j][k] = l;
}
}
}
}
}
double ans = 0;
int ansi = -1,ansj = -1;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
{
if(ans < dp[i][j][m])
{
ans = dp[i][j][m];
ansi = i;
ansj = j;
}
}
// cout << dp[ansi][ansj][m] << endl;
vector<int> res;
int k = m;
while(ansj)
{
// printf(">>%d\n",a[ansj].idx);
res.push_back(a[ansj].idx);
ansj = pre[ansi][ansj][k];
k -= 1;
}
res.push_back(a[ansi].idx);
sort(res.begin(),res.end());
reverse(res.begin(),res.end());
for(int i = 0;i < m;++i)
printf("%d%c",res[i] - 1," \n"[i == m - 1]);
return 0;
}
[AHOI2009]CHESS 中国象棋
首先考虑的是如果n和m都是小于8的。
这时候我们会考虑使用状态压缩来求，设第i行的状态为s，所选的列有几个1进行转移。
但是这个n,m最大可以到100？这样怎么求解呢？
考虑优化，我们知道具体哪一列有1很重要吗？显然不是，由于一行符合要求的最多就只有2个1，那么我们直接把这个加入状态即可：
设dp[i][j][k]表示前i行，有j个列没有1，k个列有1个1，m - j - k个列有2个1的符合要求的摆放个数
然后就可以做如下的转移：
第i列放一个
1、放在那j列中
k >= 1
dp[i][j][k] += dp[i - 1][j + 1][k - 1] * (j + 1);
2、放在那k列中
m - j - k >= 1
dp[i][j][k] += dp[i - 1][j][k + 1] * (k + 1);
第i列放了2个
1、都放在那没放的列中
k >= 2
dp[i][j][k] += dp[i - 1][j + 2][k - 2] * (j * (j - 1))
2、都放在放了一个的列中
m - j - k >= 2
dp[i][j][k] += dp[i - 1][j][k + 2] * (k * (k - 1))
3、一个放在了无球的列中，一个放在了有一个球的列中
m - j - k >= 1
dp[i][j][k] += dp[i - 1][j + 1][k] * (2 * (j + 1) * (k + 1))
AC代码：
点击查看代码
#include <iostream>
using namespace std;
const int MAXN = 1e2 + 7;
const int MOD = 9999973;
typedef long long ll;
ll dp[MAXN][MAXN][MAXN];//前i行 有j列是啥也没放的，k列是放了一个的 m - j - k是放了两个的
/*
第i列放一个
1、放在那j列中
k >= 1
dp[i][j][k] += dp[i - 1][j + 1][k - 1] * (j + 1);
2、放在那k列中
m - j - k >= 1
dp[i][j][k] += dp[i - 1][j][k + 1] * (k + 1);
第i列放了2个
1、都放在那没放的列中
k >= 2
dp[i][j][k] += dp[i - 1][j + 2][k - 2] * (j * (j - 1))
2、都放在放了一个的列中
m - j - k >= 2
dp[i][j][k] += dp[i - 1][j][k + 2] * (k * (k - 1))
3、一个放在了无球的列中，一个放在了有一个球的列中
m - j - k >= 1
dp[i][j][k] += dp[i - 1][j + 1][k] * (2 * (j + 1) * (k + 1))
*/
/*
50 12
*/
int main()
{
int n,m;
scanf("%d %d",&n,&m);
dp[0][m][0] = 1;
for(int i = 1;i <= n;++i)
{
for(int j = 0;j <= m;++j)
for(int k = 0;k + j <= m;++k)
{
int p = m - j - k;
dp[i][j][k] += dp[i - 1][j][k];
if(k >= 1)
dp[i][j][k] += dp[i - 1][j + 1][k - 1] * (j + 1) % MOD;
dp[i][j][k] %= MOD;
if(p >= 1)
dp[i][j][k] += dp[i - 1][j][k + 1] * (k + 1) % MOD;
dp[i][j][k] %= MOD;
if(k >= 2)
dp[i][j][k] += dp[i - 1][j + 2][k - 2] * ((j + 2) * (j + 1) / 2) % MOD;
dp[i][j][k] %= MOD;
if(p >= 2)
dp[i][j][k] += dp[i - 1][j][k + 2] * ((k + 2) * (k + 1) / 2) % MOD;
dp[i][j][k] %= MOD;
if(p >= 1 && k >= 1)
dp[i][j][k] += dp[i - 1][j + 1][k] * ((j + 1) * k) % MOD;
dp[i][j][k] %= MOD;
}
}
ll ans = 0;
for(int i = 0;i <= m;++i)
for(int j = 0;j + i <= m;++j)
ans = (ans + dp[n][i][j]) % MOD;
printf("%lld\n",ans);
}
区间价值
考虑如果已知了长度为i - 1的区间价值之后，怎么推导长度为i的区间价值？
看个例子稍微理解理解：
1 2 4 2 2
长度为2的区间
1 2、2 4、4 2、2 2
答案：
2、2、2、1
长度为3的区间
1 2 4、2 4 2、4 2 2
答案
3、2、2
可以看见
F[1 2 4] = F[1 2] + 1;
F[2 4 2] = F[2 4] + 0;
F[4 2 2] = F[4 2] + 0;
最后还要减去最后一个长度为i - 1区间的那个答案
那么我们的转移方程可以写成这样：
dp[i] = dp[i + 1] + G[i] - dif[i - 1];
考虑G[i]怎么求：
观察上诉例子，可以发现会影响G[i]的只会和下标为3 4 5的值有关
可以找见，如果上诉下标所代表的值上一次出现的位置和当前位置的距离差>=i，那么就会对答案贡献一个1
即G[i] = 长度为n的序列中相同大小数字长度 >= i的二元组出现的个数
这个我们可以一遍O(n)求长度为i的二元组有多少个，然后对其求一个后缀和即可
对于dif[i],从序列的最后一个元素开始往前扫，统计其后缀区间价值即可
AC代码：
点击查看代码
#include <iostream>
using namespace std;
const int MAXN = 1e6 + 7;
int a[MAXN];
typedef long long ll;
ll dp[MAXN];
ll pre[MAXN],det[MAXN],dif[MAXN];
bool vis[MAXN];
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]);
for(int i = 1;i <= n;++i)
{
det[i - pre[a[i]]] += 1;
pre[a[i]] = i;
}
for(int i = n;i >= 1;--i) det[i] = det[i + 1] + det[i];
int cnt = 0;
for(int i = n;i >= 1;--i)
{
if(!vis[a[i]])
{
cnt += 1;
vis[a[i]] = 1;
}
dif[n - i + 1] = cnt;
}
dp[0] = 0;
for(int i = 1;i <= n;++i)
dp[i] = dp[i - 1] + det[i] - dif[i - 1];
int q;
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
printf("%lld\n",dp[x]);
}
return 0;
}
排列游戏
由于只具有三种情况0 1 2,0的情况是随意的，我们看一下1 和 2对答案会产生什么影响
1 : a[i] < a[i + 1]
2 : a[i] > a[i + 1]
那么其实当前第i位其实之和前一位有关，而且和前一位具体是什么数字有关
设dp[i][j]代表前i位数字，当前第i位填的是j的方案数
如果当前的约束是0：
dp[i][j] = sum(dp[i - 1][k]) k ∈ [1,i - 1]
因为我想填什么数在第i - 1位都是可行的
约束是1：
dp[i][j] = sum(dp[i - 1][k]) k ∈ [1,j - 1]
因为前一位要小于j
约束是2：
dp[i][j] = sum(dp[i - 1][k]) k ∈ [j - 1,i - 1]
因为j要小于前一位；
很多人这时候有个疑问，上诉区间左界为什么是j - 1而不是j
我在这就做一个简单的感性理解吧...（555
因为前i - 1位的数字已经构成了一个排列，现在是多加入了一个数字i
在第i位添加一个数字j；
相当于前i位中的数字 > j位置上的数字都增加1(这样好让i加入前i - 1个位置当中，显然这时候少了一个j,前i - 1个位置上的数还是能保持和i - 1的排列一样的结果...)
因此反过来就相当于第i位添加的数是j - 1，因此左界是j - 1
AC代码：
点击查看代码
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 5e3 + 7;
const int MOD = 998244353;
ll dp[MAXN][MAXN],su[MAXN];
char s[MAXN];
/*
000000
*/
int main()
{
scanf(" %s",s + 1);
int n = strlen(s + 1);
dp[1][1] = 1;
su[1] = 1;
for(int i = 2;i <= n + 1;++i)
{
for(int j = 1;j <= i;++j)
if(s[i - 1] == '0')
dp[i][j] = su[i - 1];
else if(s[i - 1] == '1')
dp[i][j] = su[j - 1];
else dp[i][j] = (su[i - 1] - su[j - 1] + MOD) % MOD;
for(int j = 1;j <= i;++j)
su[j] = (su[j - 1] + dp[i][j]) % MOD;
}
ll ans = su[n + 1];
// for(int i = 1;i <= n + 1;++i)
// (ans += dp[n + 1][i]) % MOD;
printf("%lld\n",ans);
return 0;
}
[ZJOI2008]骑士
前置题目：没有上司的舞会
这道题多出来的就是对于一颗树，多了一条边，使其中存在环...
那么我们这样考虑，将该环断开，然后又得到一棵树，对断开边的两个端点来说，我们如果要拿的话，只会拿走其中的一个。
那么我们只需要对这两个端点进行树形DP。然后两个端点分别不取中取一个最大值就是答案。
这里有一个坑就是，题目中构成的基环树可能不止一个
AC代码：
点击查看代码
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 7;
typedef long long ll;
const ll inf = 1e12;
struct node{
int ne,to,w;
}a[MAXN << 2];
int head[MAXN],cnt = 0;
void add(int x,int y,int w = 0)
{
a[++cnt].ne = head[x];
head[x] = cnt;
a[cnt].w = w;
a[cnt].to = y;
}
ll A[MAXN];
bool vis[MAXN];
int fa[MAXN],root = 0;
ll dp[MAXN][2];
/*
8
1 2
1 5
1 1
1 2
1 6
1 3
1 8
1 7
*/
bool v[MAXN];
int p1,p2;
void dfs(int x,int fa)
{
vis[x] = 1;
for(int i = head[x];i;i = a[i].ne)
{
int y = a[i].to;
if(y == fa) continue;
if(vis[y])
p1 = x,p2 = y;
else
dfs(y,x);
}
}
vector<int> tmp;
void go(int x,int fa)
{
dp[x][0] = 0;
dp[x][1] = A[x];
v[x] = 1;
tmp.push_back(x);
for(int i = head[x];i;i = a[i].ne)
{
int y = a[i].to;
if(y == fa || v[y])
continue;
go(y,x);
dp[x][1] += dp[y][0];
dp[x][0] += max(dp[y][1],dp[y][0]);
}
}
void clear()
{
for(int i = 0;i < tmp.size();++i) v[tmp[i]] = 0;
tmp.clear();
}
ll solve(int x)
{
ll ans = 0;
dfs(x,-1);
root = p1;
go(root,-1);clear();
ans = max(ans,dp[root][0]);
root = p2;
go(root,-1);clear();
ans = max(ans,dp[root][0]);
return ans;
}
/*
3
100 2
100 1
12 1
*/
int main()
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n;++i)
{
int ha;
scanf("%lld %d",&A[i],&ha);
fa[i] = ha;
add(ha,i);
add(i,ha);
}
ll ans = 0;
for(int i = 1;i <= n;++i)
if(!vis[i])
ans += solve(i);
printf("%lld\n",ans);
return 0;
}