社区讨论

求助!!!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 条回复,欢迎继续交流。

正在加载回复...