当前位置:网站首页>AtCoder Beginner Contest 237 VP补题
AtCoder Beginner Contest 237 VP补题
2022-07-02 15:15:00 【sophilex】
大意:
给定一张无向图,两点间的边权:
较高点到较低点的边权等于高度差
较低点到较高点的边权等于高度差的负二倍
求:图中的最大dis值
思路:
按题意建边即可;
但是有负权,所以一般的dij不行。
赛后又加强过数据,所以我跑了spfa,T烂了。。。(但是我看有一个哥们还真用spfa冲过去了。。。【崩溃】)
官方题解的思路是dij
考虑“势”的思想(绝):
对数据进行预处理,高点到低点的边权等于0,低点到高点的距离等于高度差(>=0)
那么就全是非负权边了。
跑完dij后只要把数据还原回去就可以了,dis[i]=h[i]-h[1]+dist[i]
code:
再说
大意:
求长度为 n,每个元素不大于m的序列,满足以下条件的有多少种:
最长上升子序列长度恰好为3.
思路:
m很小,只有10,那么久很容易想到暴力枚举+dp
不妨设i代表当前枚举到的数列长度,k1 表示当前序列长度为1的LIS的最后一个元素的最小值,k2 表示当前序列长度为2的LIS的最后一个元素的最小值,k3 则表示当前序列长度为3的LIS的最后一个元素的最小值
那么dp[i][k1][k2][k3]就代表对应情况的方案数。
那么每次再多枚举一个x,对x的大小进行分类讨论即可。
细节见code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1005;
const ll mod=998244353;
ll dp[N][12][12][12];
ll n,m;
int main()
{
cin>>n>>m;
dp[0][m+1][m+1][m+1]=1;
for(int i=1;i<=n;++i)
{
for(int k1=1;k1<=m+1;++k1)
{
for(int k2=1;k2<=m+1;++k2)
{
for(int k3=1;k3<=m+1;++k3)
{
for(int x=1;x<=m;++x)
{
if(x<=k1) dp[i][x][k2][k3]=(dp[i-1][k1][k2][k3]+dp[i][x][k2][k3])%mod;
else if(x<=k2) dp[i][k1][x][k3]=(dp[i-1][k1][k2][k3]+dp[i][k1][x][k3])%mod;
else if(x<=k3) dp[i][k1][k2][x]=(dp[i-1][k1][k2][k3]+dp[i][k1][k2][x])%mod;
}
}
}
}
}
ll ans=0;
for(int k1=1;k1<=m;++k1)
{
for(int k2=1;k2<=m;++k2)
{
for(int k3=1;k3<=m;++k3)
{
// cout<<dp[n][k1][k2][k3];
ans=(ans+dp[n][k1][k2][k3])%mod;
}
}
}
cout<<ans<<endl;
return 0;
}
边栏推荐
- ThreadLocal
- 宝宝巴士创业板IPO被终止:曾拟募资18亿 唐光宇控制47%股权
- Briefly introduce the use of base64encoder
- Qstype implementation of self drawing interface project practice (II)
- 深度之眼(三)——矩阵的行列式
- vector的底层模拟实现
- Niuke js3 separator
- ThreadLocal
- Weili holdings listed on the Hong Kong Stock Exchange: with a market value of HK $500million, it contributed an IPO to Hubei
- SAP Commerce Cloud 架构概述
猜你喜欢
ThreadLocal
A few lines of code to complete RPC service registration and discovery
阿里天池SQL学习笔记——DAY3
剑指 Offer 22. 链表中倒数第k个节点
Sword finger offer 21 Adjust the array order so that odd numbers precede even numbers
Eth data set download and related problems
Blog theme "text" summer fresh Special Edition
Connect Porsche and 3PL EDI cases
智能垃圾桶(五)——点亮OLED
QWebEngineView崩溃及替代方案
随机推荐
Microservice architecture practice: Construction of highly available distributed file system fastdfs architecture
Niuke js3 separator
dstat使用[通俗易懂]
线性规划例题 投资的收益与风险
PCL知识点——体素化网格方法对点云进行下采样
超卓航科上市:募资9亿市值超60亿 成襄阳首家科创板企业
常用SQL语句(完整范例)
Listing of chaozhuo Aviation Technology Co., Ltd.: raising 900million yuan, with a market value of more than 6billion yuan, becoming the first science and technology innovation board enterprise in Xia
Sword finger offer 22 The penultimate node in the linked list
Eth data set download and related problems
QStyle实现自绘界面项目实战(二)
Chmod command principle and usage details [easy to understand]
綠竹生物沖刺港股:年期內虧損超5億 泰格醫藥與北京亦莊是股東
2020 "Lenovo Cup" National College programming online Invitational Competition and the third Shanghai University of technology programming competition (a sign in, B sign in, C sign in, D thinking +mst
酒仙网IPO被终止:曾拟募资10亿 红杉与东方富海是股东
SSB threshold_ SSB modulation "suggestions collection"
LeetCode:1380. Lucky number in matrix -- simple
871. 最低加油次数
剑指 Offer 26. 树的子结构
Alibaba Tianchi SQL learning notes - Day3