欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

hdu5693 D gamehdu 5712 D++ game

发布时间:2024/7/5 编程问答 0 豆豆
如意编程网 收集整理的这篇文章主要介绍了 hdu5693 D gamehdu 5712 D++ game 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目链接:5693

题目链接:5712

对于这个D game。注意消除之后两遍的序列是可以拼合到一起的!我们可以想到有区间DP的做法。我们设\(f[i][j]\)表示区间i,j可以被消除。

显然如果这个区间可以被消除,则操作一定可以被分解成一次消除两个k1次,一次消除三个k2次。所以我们只考虑消除两个和消除三个的情况即可。

开始可以把公差放进set里面,方便之后查询。

具体转移见代码。

处理完哪些区间可以被消除之后,我们可以利用贪心来计算最大消除的数量。(要先把可行区间放入到一个vector里面,然后排序,按照长度为第一关键字,左端点为第二关键字。因为大区间一定覆盖它里面的小区间,所以我们只要遇到自己区间已经被计算过了就不用计算这整个区间了)。

代码如下:

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<set> #include<vector> #define MAXN 310 using namespace std; int t,n,m,cur,ans; struct Edge{int l,r,dis;}; int a[MAXN],f[MAXN][MAXN],done[MAXN],dp[MAXN]; set<int>s; vector<Edge>v; inline bool cmp(struct Edge x,struct Edge y) { if(x.dis==y.dis) return x.l<y.l;return x.dis>y.dis; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d",&t);while(t--){ans=0;s.clear();v.clear();memset(f,0,sizeof(f));memset(done,0,sizeof(done));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i][i-1]=1;for(int i=1;i<=m;i++) scanf("%d",&cur),s.insert(cur);for(int i=1;i<=n;i++){for(int l=1;l+i<=n;l++){int r=l+i;//printf("l=%d r=%d\n",l,r);if(f[l+1][r-1]&&s.count(a[r]-a[l])) f[l][r]=1;if(!f[l][r]){for(int k=l+1;k<=r-1;k++){int cha1=a[r]-a[k],cha2=a[k]-a[l];if((f[l][k-1]&&f[k][r])||(f[l+1][k-1]&&f[k+1][r-1]&&cha1==cha2&&s.count(cha1))){f[l][r]=1;break;}}}}}for(int i=1;i<=n-1;i++)for(int j=i+1;j<=n;j++)if(f[i][j])v.push_back((Edge){i,j,j-i+1});sort(v.begin(),v.end(),cmp);int cur=0;for(int i=0;i<v.size();i++){bool flag=true;for(int j=v[i].l;j<=v[i].r;j++)if(done[j]==1){flag=false;break;}if(flag==false) continue;for(int j=v[i].l;j<=v[i].r;j++)done[j]=1;}for(int i=1;i<=n;i++) if(done[i]) ans++;printf("%d\n",ans);}return 0; }

然后对于那个加强版。
我想的是因为它的公差的种类数量很少,所以我想的是直接记录一下哪个区间里面有多少种公差,那么就知道了消除这个区间至少需要多少次。但是这样的话没有办法判断一次消除到底有没有满足消除数量在min,max范围内。。。。

所以说这个题我还木有A掉。。。。但是在网上也没有找到题解。。。。就先把自己WA的代码放在这里好了。。。

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<set> #include<vector> #include<map> #define MAXN 100 using namespace std; int t,n,m,cur,ans,minn,maxx,cnt,kkk; struct Edge{int l,r,dis;}; struct Node{int sum[40];}node[MAXN][MAXN]; int a[MAXN],f[MAXN][MAXN],done[MAXN],dp[MAXN]; set<int>s; vector<Edge>v; map<int,int>id; inline bool cmp(struct Edge x,struct Edge y) { if(x.dis==y.dis) return x.l<y.l;return x.dis>y.dis; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d",&t);while(t--){kkk++;ans=cnt=0;s.clear();v.clear();memset(f,0,sizeof(f));memset(done,0,sizeof(done));scanf("%d%d%d%d",&n,&m,&minn,&maxx);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++) scanf("%d",&cur),s.insert(cur),id[cur]=i;for(int i=1;i<=n;i++) {f[i][i-1]=1;if(s.count(a[i+1]-a[i]))node[i][i-1].sum[id[a[i+1]-a[i]]]=1;}for(int i=1;i<=n;i++){for(int l=1;l+i<=n;l++){int r=l+i;if(f[l+1][r-1]&&s.count(a[r]-a[l])&&a[r]!=a[r-1]&&a[l]!=a[l+1]) { f[l][r]=1;for(int k=1;k<=32;k++) node[l][r].sum[k]=node[l+1][r-1].sum[k];node[l][r].sum[id[a[r]-a[l]]]=1;}vector<int>put,cur_ans;if(!f[l][r]){for(int k=l+1;k<=r-1;k++){int cha1=a[r]-a[k],cha2=a[k]-a[l];if(f[l][k-1]&&f[k][r]&&a[k]!=a[k-1]){f[l][r]=1;put.clear();for(int p=1;p<=32;p++)if(node[l][k-1].sum[p]||node[k][r].sum[p])put.push_back(p);if(cur_ans.size()==0)for(int q=0;q<put.size();q++)cur_ans.push_back(put[q]);if(cur_ans.size()!=0&&put.size()<cur_ans.size()){cur_ans.clear();for(int q=0;q<put.size();q++)cur_ans.push_back(put[q]);}}if(f[l+1][k-1]&&f[k+1][r-1]&&cha1==cha2&&s.count(cha1)){if(a[l]==a[l+1]||a[k-1]==a[k]||a[k]==a[k+1]||a[r-1]==a[r]) continue;f[l][r]=1;put.clear();for(int p=1;p<=32;p++)if(node[l+1][k-1].sum[p]||node[k+1][r-1].sum[p]||p==id[cha1])put.push_back(p);if(cur_ans.size()==0)for(int q=0;q<put.size();q++)cur_ans.push_back(put[q]);if(cur_ans.size()!=0&&put.size()<cur_ans.size()){cur_ans.clear();for(int q=0;q<put.size();q++)cur_ans.push_back(put[q]);}}}}if(f[l][r])for(int k=0;k<cur_ans.size();k++) node[l][r].sum[cur_ans[k]]=1;}}for(int i=1;i<=n-1;i++)for(int j=i+1;j<=n;j++)if(f[i][j])v.push_back((Edge){i,j,j-i+1});sort(v.begin(),v.end(),cmp);int cnt=0;for(int i=0;i<v.size();i++){if(v[i].dis<minn) continue;//int k1=v[i].dis/minn;//if((maxx-minn)*k<v[i].dis-k*minn) continue;int k=v[i].dis/maxx+(v[i].dis%maxx==0?0:1);if((v[i].dis%maxx!=0)&&(v[i].dis%maxx+(k-1)*(maxx-minn)<minn)) continue;bool flag=true;for(int j=v[i].l;j<=v[i].r;j++)if(done[j]==1){flag=false;break;}if(flag==false) continue;for(int j=v[i].l;j<=v[i].r;j++)done[j]=1;for(int j=1;j<=32;j++)if(node[v[i].l][v[i].r].sum[j])cnt++;}for(int i=1;i<=n;i++) if(done[i]) ans++;printf("Case #%d:\n%d %d\n",kkk,ans,cnt);}return 0; }

转载于:https://www.cnblogs.com/fengxunling/p/10351015.html

总结

以上是如意编程网为你收集整理的hdu5693 D gamehdu 5712 D++ game的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。