从色彩度讨论如何建设一个网站.,景区网站建设策划案,朋友圈推广广告,连云港网站备案在哪题目链接#xff1a;5693 题目链接#xff1a;5712 对于这个D game。注意消除之后两遍的序列是可以拼合到一起的#xff01;我们可以想到有区间DP的做法。我们设\(f[i][j]\)表示区间i,j可以被消除。 显然如果这个区间可以被消除#xff0c;则操作一定可以被分解成一次消除两… 题目链接5693 题目链接5712 对于这个D game。注意消除之后两遍的序列是可以拼合到一起的我们可以想到有区间DP的做法。我们设\(f[i][j]\)表示区间i,j可以被消除。 显然如果这个区间可以被消除则操作一定可以被分解成一次消除两个k1次一次消除三个k2次。所以我们只考虑消除两个和消除三个的情况即可。 开始可以把公差放进set里面方便之后查询。 具体转移见代码。 处理完哪些区间可以被消除之后我们可以利用贪心来计算最大消除的数量。要先把可行区间放入到一个vector里面然后排序按照长度为第一关键字左端点为第二关键字。因为大区间一定覆盖它里面的小区间所以我们只要遇到自己区间已经被计算过了就不用计算这整个区间了。 代码如下 #includeiostream
#includecstring
#includecstdio
#includealgorithm
#includeset
#includevector
#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];
setints;
vectorEdgev;
inline bool cmp(struct Edge x,struct Edge y)
{ if(x.disy.dis) return x.ly.l;return x.disy.dis;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(ce.in,r,stdin);#endifscanf(%d,t);while(t--){ans0;s.clear();v.clear();memset(f,0,sizeof(f));memset(done,0,sizeof(done));scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]),f[i][i-1]1;for(int i1;im;i) scanf(%d,cur),s.insert(cur);for(int i1;in;i){for(int l1;lin;l){int rli;//printf(l%d r%d\n,l,r);if(f[l1][r-1]s.count(a[r]-a[l])) f[l][r]1;if(!f[l][r]){for(int kl1;kr-1;k){int cha1a[r]-a[k],cha2a[k]-a[l];if((f[l][k-1]f[k][r])||(f[l1][k-1]f[k1][r-1]cha1cha2s.count(cha1))){f[l][r]1;break;}}}}}for(int i1;in-1;i)for(int ji1;jn;j)if(f[i][j])v.push_back((Edge){i,j,j-i1});sort(v.begin(),v.end(),cmp);int cur0;for(int i0;iv.size();i){bool flagtrue;for(int jv[i].l;jv[i].r;j)if(done[j]1){flagfalse;break;}if(flagfalse) continue;for(int jv[i].l;jv[i].r;j)done[j]1;}for(int i1;in;i) if(done[i]) ans;printf(%d\n,ans);}return 0;
} 然后对于那个加强版。 我想的是因为它的公差的种类数量很少所以我想的是直接记录一下哪个区间里面有多少种公差那么就知道了消除这个区间至少需要多少次。但是这样的话没有办法判断一次消除到底有没有满足消除数量在min,max范围内。。。。 所以说这个题我还木有A掉。。。。但是在网上也没有找到题解。。。。就先把自己WA的代码放在这里好了。。。 #includeiostream
#includecstring
#includecstdio
#includealgorithm
#includeset
#includevector
#includemap
#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];
setints;
vectorEdgev;
mapint,intid;
inline bool cmp(struct Edge x,struct Edge y)
{ if(x.disy.dis) return x.ly.l;return x.disy.dis;
}
int main()
{#ifndef ONLINE_JUDGEfreopen(ce.in,r,stdin);#endifscanf(%d,t);while(t--){kkk;anscnt0;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 i1;in;i) scanf(%d,a[i]);for(int i1;im;i) scanf(%d,cur),s.insert(cur),id[cur]i;for(int i1;in;i) {f[i][i-1]1;if(s.count(a[i1]-a[i]))node[i][i-1].sum[id[a[i1]-a[i]]]1;}for(int i1;in;i){for(int l1;lin;l){int rli;if(f[l1][r-1]s.count(a[r]-a[l])a[r]!a[r-1]a[l]!a[l1]) { f[l][r]1;for(int k1;k32;k) node[l][r].sum[k]node[l1][r-1].sum[k];node[l][r].sum[id[a[r]-a[l]]]1;}vectorintput,cur_ans;if(!f[l][r]){for(int kl1;kr-1;k){int cha1a[r]-a[k],cha2a[k]-a[l];if(f[l][k-1]f[k][r]a[k]!a[k-1]){f[l][r]1;put.clear();for(int p1;p32;p)if(node[l][k-1].sum[p]||node[k][r].sum[p])put.push_back(p);if(cur_ans.size()0)for(int q0;qput.size();q)cur_ans.push_back(put[q]);if(cur_ans.size()!0put.size()cur_ans.size()){cur_ans.clear();for(int q0;qput.size();q)cur_ans.push_back(put[q]);}}if(f[l1][k-1]f[k1][r-1]cha1cha2s.count(cha1)){if(a[l]a[l1]||a[k-1]a[k]||a[k]a[k1]||a[r-1]a[r]) continue;f[l][r]1;put.clear();for(int p1;p32;p)if(node[l1][k-1].sum[p]||node[k1][r-1].sum[p]||pid[cha1])put.push_back(p);if(cur_ans.size()0)for(int q0;qput.size();q)cur_ans.push_back(put[q]);if(cur_ans.size()!0put.size()cur_ans.size()){cur_ans.clear();for(int q0;qput.size();q)cur_ans.push_back(put[q]);}}}}if(f[l][r])for(int k0;kcur_ans.size();k) node[l][r].sum[cur_ans[k]]1;}}for(int i1;in-1;i)for(int ji1;jn;j)if(f[i][j])v.push_back((Edge){i,j,j-i1});sort(v.begin(),v.end(),cmp);int cnt0;for(int i0;iv.size();i){if(v[i].disminn) continue;//int k1v[i].dis/minn;//if((maxx-minn)*kv[i].dis-k*minn) continue;int kv[i].dis/maxx(v[i].dis%maxx0?0:1);if((v[i].dis%maxx!0)(v[i].dis%maxx(k-1)*(maxx-minn)minn)) continue;bool flagtrue;for(int jv[i].l;jv[i].r;j)if(done[j]1){flagfalse;break;}if(flagfalse) continue;for(int jv[i].l;jv[i].r;j)done[j]1;for(int j1;j32;j)if(node[v[i].l][v[i].r].sum[j])cnt;}for(int i1;in;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
