4091. 括号序列
#include<iostream>
#define int long long
using namespace std;
const int N=5e2+10;
const int mod=1e9+7;
long long f[N][N][6];
/*
f(i,j,0):[i,j]中全部填'*'的方案数
f(i,j,1):[i,j]中构成(.....)类型的方案数
(即内部合法串刚好被一对括号包住)
f(i,j,2):[i,j]中构成(.....)**(...)***类型的方案数
(即以括号开头，以'*'结尾)
f(i,j,3):[i,j]中构成(.....)***(.....)**(..)类型的方案数
(即以括号开头，以括号结尾)
f(i,j,4):[i,j]中构成*****(....)**(...)类型的方案数
(即以'*'开头，以括号结尾)
f(i,j,5):[i,j]中构成***(...)**(....)***类型的方案数
(即以'*'开头，以'*'结尾)
转移：
1.f(i,j,0)=f(i,j-1,0)&check(j);
首先，先让f(i,j,0)继承f(i,j-1,0)
但我们要判断一下f(i,j,0)有没有继承的资格
check(j)即判断第j个字符为'*'或'?'
为'*'很好理解，为'?'即可以将该字符变为'*'
这个特判一下长度是否小于m，满足即可转移
2.if cmp(i,j):
f(i,j,1)=f(i+1,j-1,0)+f(i+1,j-1,2)+f(i+1,j-1,3)+f(i+1,j-1,4)
因为题目中已经给出了特例，*(...)*类型的串非合法括号序列，因此里面不可以加f(i+1,j-1,5)
cmp(i,j)是判断s(i)与s(j)能否构成一对括号
如果这个都不满足就不要转移了
下面定义k,有i<=k<j,即区间DP中的中间点
3. f(i,j,2)+=f(i,k,3)*f(k+1,j,0)
根据定义，你要先构造一段以括号开头，以括号结尾的合法串
很明显,只有f(i,k,3)满足条件
你要再接上一段'*'构成的串，即f(k+1,j,0)
为什么没有f(i,k,2)?
因为f(i,k,2)最后会有一段'*',而它可以与f(k+1,j,0)中的'*'自动连成一段
所以在这里不考虑
4. f(i,j,3)+=(f(i,k,2)+f(i,k,3))*f(k+1,j,1)+f(i,j,0)
可知:前一段开头为括号，结尾随便
可以发现f(i,k,2)与f(i,k,3)均符合条件
结尾与f(i,j,2)类似，搞出有一对括号，里面有合法串构成的字符串即可
因为f(i,j,1)也符合f(i,j,3)的条件，因此要单独加上
5.f(i,j,4)+=(f(i,k,4)+f(i,k,5))*f(k+1,j,0)
可知:前一段开头为'*'，结尾随便
可以发现f(i,k,4)与f(i,k,5)均符合条件
结尾与f(i,j,2)完全一样
6. f(i,j,4)+=f(i,k,4)*f(k+1,j,0)+f(i,j,0)
可知:前一段开头为'*'，结尾随为'*'
可以发现只有f(i,k,4)符合条件
结尾与f(i,j,2)与f(i,j,4)完全一样
与f(i,j,3)类似,最后要加上f(i,j,0)
最后,应输出满足是合法序列的情况
有f(1,n,1)与f(1,n,3)
因为f(1,n,1)的方案一定包含在f(1,n,3)中
因此只输出f(1,n,3)就好了
*/
int n,m;
char s[N];
int cmp(int l,int r){
if((s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')){
return 1;
}
return 0;
}
inline bool check(int j){
if(s[j]=='*'||s[j]=='?'){
return 1;
}
return 0;
}
inline void get(int &x,int y){
x+=y;
int d=x/mod;
x-=d*mod;
}
signed main(){
cin>>n>>m;
scanf("%s",s+1);
for(int i=1;i<=n;i++){
f[i][i-1][0]=1;
}
for(int i=n;i;i--){
for(int j=i;j<=n;j++){
int len=j-i+1;
if(len<=m){
f[i][j][0]=f[i][j-1][0]&check(j);
}
if(len>1){
if(cmp(i,j)){
get(f[i][j][1],(f[i+1][j-1][0]+f[i+1][j-1][2]+f[i+1][j-1][3]+f[i+1][j-1][4]));
}
// cout<<cmp(i,j)<<' ';
for(int k=i;k<j;k++){
get(f[i][j][2],f[i][k][3]*f[k+1][j][0]);
get(f[i][j][3],(f[i][k][2]+f[i][k][3])*f[k+1][j][1]);
get(f[i][j][4],(f[i][k][4]+f[i][k][5])*f[k+1][j][1]);
get(f[i][j][5],f[i][k][4]*f[k+1][j][0]);
}
}
get(f[i][j][3],f[i][j][1]);
get(f[i][j][5],f[i][j][0]);
// cout<<i<<' '<<j<<' ';
// for(int k=0;k<=5;k++){
// cout<<f[i][j][k]<<' ';
// }
// cout<<endl;
}
// for(int i=1;i<=n;i++){
// f[i][i-1][0]=0;
// }
}
// for(int i=0;i<=n;i++){
// cout<<f[1][n][0]<<endl;
// }
cout<<f[1][n][3];
return 0;
}
4088. 网络连接
#include<iostream>
#include<unordered_map>
using namespace std;
int idx;
unordered_map<string,int> f;
//哈希表，用来映射
//用map也可以，只是多一个log
bool check(string s){
int cnt=0,cnt2=0;
//记录点与冒号的数量
//可以用于查该字符串是否合法
int x=s.size();
for(int i=0;i<x;i++){
if(!isdigit(s[i])&&s[i]!=' '){
if(s[i]=='.'){
cnt++;
}else if(s[i]==':'){
cnt2++;
}
//计数
}
}
if(cnt!=3||cnt2!=1){
return 0;
}//判断是否合法
int siz=0,sum=-1;
/*
siz:当前数值的位数
sum:具体数值
*/
//sum=-1是因为两个非数字字符中间没有数字字符
//这样也是不合法的
int la=0;
/*
记录最后一个非数字字符出现的位置
用来确定是否到了最后一个数字
*/
for(int i=x-1;~i;i--){
if(!isdigit(s[i])){
la=i;
break;
}
}
/*
这样方便判断是否合法
(因为前4个数与最后一个数的合法范围不同)
*/
int fi=10;
//记录该数值的第一位数字
for(int i=0;i<x;i++){
if(sum>255&&i<=la){
return 0;
}
if(sum>65535){
return 0;
}
/*
因为每一个数值必定小于65536
这里我怕数值会爆掉(太大了)，所以提前判断掉
(免得我后面死活调不出来)
*/
//根据数值判断是否合法
if(!isdigit(s[i])){
if(sum==-1){
return 0;
}//中间没有数
//下面处理前导零问题
if(sum==0&&siz>1){
return 0;//数值为0但长度大于1
}else if(sum>0&&!fi){
return 0;//数值不为0但是以0开头
}
//判断对应字符是否正确
if(i==la&&s[i]!=':'){
return 0;
}else if(i!=la&&s[i]!='.'){
return 0;
}
siz=0,sum=-1,fi=10;
//初始化
continue;
}
if(fi==10){
fi=s[i]-'0';
}//找到该数值的第一个数字
if(sum==-1){
sum=s[i]-'0';
}else{
sum=sum*10+(s[i]-'0');
}//算该数值具体是多少
siz++;//数值位数加1，方便上面的判断
}
//以下是单独处理最后一个数
if(sum<0){
return 0;
}
if(sum>65535||(sum==0&&siz>1)||(sum>0&&fi==0)){
return 0;
}
//如果以上条件均满足，即合法
return 1;
}
int main(){
int t;
cin>>t;
getchar();
while(t--){
idx++;
string s,t;
cin>>s>>t;
/*
这里为方便，分两个部分读入
s:是服务器还是客户机
t:地址
*/
if(!check(t)){
puts("ERR");
continue;//不合法即直接ERR
}
//以下是分类讨论
if(s[0]=='S'){
if(f[t]){
puts("FAIL");
//已经出现过，即无法链接
}else{
puts("OK");
f[t]=idx;//记录该地址对应服务器的编号
}
}else{
if(!f[t]){
puts("FAIL");
//没有该服务器
}else{
printf("%d\n",f[t]);//有，输出服务器编号
}
}
}
return 0;
}
2770. 方格取数
#include<iostream>
#include<cstring>
using namespace std;
int n,m;
const int N=1010;
long long a[N][N],f[N][N][3];
/*
状态定义：
f(i,j,0):从上一个格子走到当前格子能取到的最大值
f(i,j,1):从下一个格子走到当前格子能取到的最大值
f(i,j,2):从左边格子走到当前格子能取到的最大值
状态初始化：
将f数组初始化为负无穷。
起点当然要特殊处理：
f(1,1,0/1/2)=a(1,1)
可知，第一列的数只能从上往下转移而来
因此可以用递推来初始化
f(i,1,0)=f(i-1,1,0)+a(i,1)
转移顺序：
因为涉及到上与下两个方向，而左右只有向右走一个选择。
因此，我们可以考虑外层枚举列，内层枚举行。
这样方便一点。
状态转移：
f(i,j,0)=max(f(i-1,j,0),f(i-1,j,2)+a(i,j)
为什么没有f(i-1,j,1)呢？
题目中明确提到：每一个点不可以重复遍历
(i-1,j)下面的点就是(i,j)，那不就违反规定了吗？
f(i,j,1)类似：
f(i,j,1)=max(f(i-1,j,1),f(i-1,j,2)+a(i,j)
因为只能向右走，因此如果水平方向移动的话不必考虑算重：
f(i,j,2)=max(f(i,j-1,0),max(f(i,j-1,1),f(i,j-1,2)))+a(i,j)
答案：
max(f(n,m,0),max(f(n,m,1),f(n,m,2)))
当然，你可以把f(n,m,1)去掉，不影响结果
(反正(n,m)不可能从下面转移过来)
注意事项：
1.边界。不要越界(如果数组从1开始可以忽略)
2.long long。我就被坑一次
*/
int main(){
memset(f,-0x3f,sizeof f);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
f[1][1][0]=f[1][1][1]=f[1][1][2]=a[1][1];
for(int i=2;i<=n;i++){
f[i][1][0]=f[i-1][1][0]+a[i][1];
}
for(int j=2;j<=m;j++){
for(int i=1;i<=n;i++){
f[i][j][2]=max(f[i][j-1][0],max(f[i][j-1][1],f[i][j-1][2]))+a[i][j];
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][2])+a[i][j];
}
for(int i=n-1;i;i--){
f[i][j][1]=max(f[i+1][j][1],f[i+1][j][2])+a[i][j];
}
}
cout<<max(f[n][m][0],f[n][m][2]);
}
/*
总结：
普通方格取数都是要么下右、下左......
三个方向还真是头一回见。
但是只要你没搞错题意再加上一点思考，应该也是能做的。
好题！
*/
未完待续。（当然更多是写给自己看的）
