首页 > 代码库 > HDU 5009 (dp+双向链表优化)
HDU 5009 (dp+双向链表优化)
西安网络预赛题。
连续选区间填充,完全覆盖。
dp[i] 完全覆盖的最优解。
连续一起的同种颜色缩并。
优化:
1. 至多每个单独选,价值最高为N
2.不能连续选择超过sqrt(N)+1个不同的颜色
3.第i种颜色来的时候,它之前本身的颜色不再考虑。
PS:此题本来打算离散化数据,但是用map就不用了(直接判重)。对于有序的数据,离散化还要再映射
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #define MAXN (50000+5) using namespace std; int a[MAXN],b[MAXN],pre[MAXN],nxt[MAXN]; int dp[MAXN]; int main() { int N,M;pre[0]=-1;map<int,int> color; while(~scanf("%d",&N)){ for(int i=1;i<=N;i++) scanf("%d",a+i),pre[i]=i-1,nxt[i]=i+1; M=1;b[1]=a[1]; for(int i=2;i<=N;i++) if(a[i]!=a[i-1]) b[++M]=a[i]; dp[0]=0;color.clear(); for(int i=1;i<=M;i++){ if(color[b[i]]==0) color[b[i]]=i;//map判重 else{ int k=color[b[i]]; nxt[pre[k]]=nxt[k]; pre[nxt[k]]=pre[k]; color[b[i]]=i; } dp[i]=i; for(int j=i-1,k=1;j!=-1;j=pre[j],k++){ if(k>(int)sqrt(M)+1) break; int tmp=dp[j]+k*k; if(tmp>M)break; dp[i]=min(dp[i],tmp); } } printf("%d\n",dp[M]); } }
HDU 5009 (dp+双向链表优化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。