社区讨论
求助!!!unordered_map代替哈希表实现插头dp,请问哪里错了
P3190[HNOI2007] 神奇游乐园参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi7w639t
- 此快照首次捕获于
- 2025/11/21 04:36 3 个月前
- 此快照最后确认于
- 2025/11/21 04:36 3 个月前
rt
CPP//Code by muq
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<tr1/unordered_map>
#define ls c[x][0]
#define rs c[x][1]
#define ll long long
#define inf 999999999
#define io0 ios::sync_with_stdio(0)
using namespace std;
inline void muq() {
freopen("muq.in.txt", "r", stdin);
}
const int maxn = 110, maxm = 16;
int mp[maxn][maxn];
ll ans;
int c[4] = {0, -1, 1, 0};
int n, m;
tr1::unordered_map<int, ll>ht[2], T;
int now;
inline int get(int st,int x){x<<=1;return (st>>x)&3;}
inline int set(int st,int x,int val){x<<=1;return (st&(~(3<<x)))|(val<<x);}
inline int getr(int st,int x){
int r=x,cnt=-1;
while(cnt!=0)
cnt+=c[get(st,++r)];
return r;
}
inline int getl(int st,int x){
int l=x,cnt=1;
while(cnt!=0) cnt+=c[get(st,--l)];
return l;
}
inline void update(int x,int y,int st,ll val){
int p=get(st,y),q=get(st,y+1);
if(p==0&&q==0){
ht[now ^ 1][st] = max(ht[now ^ 1][st], val);//没有必须放的限制,可以不放
if(x==n-1||y==m-1) return;
int newst=set(st,y,1);newst=set(newst,y+1,2);
ht[now ^ 1][newst] = max(ht[now ^ 1][newst], val + mp[x][y]);
return;
}
if(p==0||q==0){
if(y<m-1){//往右
int newst=set(st,y,0);newst=set(newst,y+1,p+q);
ht[now ^ 1][newst] = max(ht[now ^ 1][newst], val + mp[x][y]);
}
if(x<n-1){//往下
int newst=set(st,y,p+q);newst=set(newst,y+1,0);
ht[now ^ 1][newst] = max(ht[now ^ 1][newst], val + mp[x][y]);
}
return;
}
int newst=set(st,y,0);newst=set(newst,y+1,0);
if(p==1&&q==1) newst=set(newst,getr(st,y+1),1);//合并((
if(p==2&&q==2) newst=set(newst,getl(st,y),2);//合并))
if(p==2&&q==1) ;//合并)(
if(p==1&&q==2){//合并(),统计答案
if(newst!=0) return;
ht[now ^ 1][newst] = max(ht[now ^ 1][newst], val + mp[x][y]);
ans=max(ans,val+mp[x][y]);
return;
}
ht[now ^ 1][newst] = max(ht[now ^ 1][newst], val + mp[x][y]);
}
int main(void) {
muq();
cin >> n >> m;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin >> mp[i][j];
now = 0;
ht[now].clear();
ht[now][0] = 0;
for(int i = 0; i < n; ++i) {
T.clear();
for(tr1::unordered_map<int, ll>::iterator it = ht[now].begin(); it != ht[now].end(); ++it)
T[it -> first << 2] = it -> second;
swap(T, ht[now]);
for(int j = 0; j < m; ++j) {
ht[now ^ 1].clear();
for(tr1::unordered_map<int, ll>::iterator it = ht[now].begin(); it != ht[now].end(); ++it)
update(i, j, it -> first, it -> second);
now ^= 1;
}
}
cout << ht[now][0] << endl << ans << endl;
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...