该题可以使用贪心,赛时脑子莫名把题目意思改了,导致没写出来。。。
将木棍按照pair从大到小排序,那么第一个必须要耗费准备时间删除,因为没有l,w都大于等于它的存在。
我们删除它的时候可以继续向后删除l,w都小于等于它的木棍,同时更新l,w,将所有能删的都删掉,也就是优先删最靠前的。
突然发现不会证明为什么优先删最靠前的。。。
那么只能伪证一下,越靠前越可能成为之后情况的“第一个”, 优先删前面的最有可能避免这种情况。
那贪心怎么在考试中快速发现呢?
首先有时题目中会出现“一定”的情况,利用好这个点可以将题目变的明了,贪心就变得容易一点了。
其次很多时候我们好像很难严格证明,也找不到贪心的感觉,这里,我觉得贪心的感觉主要来自更优性,相对于某某情况,某某属性的更优,贪心玄学++。
#include<bits/stdc++.h> using namespace std; #define endl '\n' typedef long long LL; typedef pair<int,int> PII; const int INF=0x3f3f3f3f; const int N=5010; PII a[N]; bool st[N]; int n; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=0;i<n;i++){ int l,w; cin>>l>>w; a[i]={l,w}; } sort(a,a+n,greater<PII>()); int res=0; for(int i=0;i<n;i++){ if(st[i])continue; st[i]=true; res++; auto [l1,w1]=a[i]; for(int j=i+1;j<n;j++){ auto [l2,w2]=a[j]; if(l2<=l1&&w2<=w1&&!st[j]){ st[j]=true; l1=l2,w1=w2; } } } cout<<res<<endl; return 0; }
第二种写法dp
此外当多个因素需要考虑时,我们不妨先将部分因素变得简单化。
如此题,有l,w2个需要考虑,我们先对l进行排序(w作为第二关键字),此时就只需要考虑w了。
当我们排序后,问题变成了求不上升子序列的最小个数,等价于求最长上升子序列的长度。
#include<bits/stdc++.h> using namespace std; #define endl '\n' typedef long long LL; typedef pair<int,int> PII; const int INF=0x3f3f3f3f; const int N=5010; int p[N],len; PII a[N]; int n; int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=0;i<n;i++){ int l,w; cin>>l>>w; a[i]={l,w}; } sort(a,a+n,greater<PII>()); for(int i=0;i<n;i++){ auto [_,x]=a[i]; int t=lower_bound(p+1,p+1+len,x)-p; p[t]=x; len=max(len,t); } cout<<len<<endl; return 0; }
wc好难的多维dp,我好像一直不怎么会这种。
再提一嘴,如果题目数据范围很小,感觉是暴搜,那么可能是用dp写的。
该题关键在于状态的表示,如果我们将15个颜色都保存下来需要开5^15,内存直接爆炸,鉴于对于我们统计方案数个个颜色都是一样的,那么我们可以将其合并,记录还剩i个的颜色有几种,同时经过一些小处理避免相邻颜色重复,这样内存就只需要15^5,解决了内存问题实际上这题就非常简单了(佬们说是水题)。
要注意的点:线性转移非常复杂,所以我们采用记忆化搜索。
同时我们要倒着来做,就是先放最后一个,理由为下。
收获:记忆化搜索时由从初始状态到0的状态情况比较好处理,边界也好处理,比较好写。
如果从0到初始状态,那么情况非常复杂,我写自闭了。。。。
#include<bits/stdc++.h> using namespace std; #define endl '\n' typedef long long LL; typedef pair<int,int> PII; const int INF=0x3f3f3f3f; const int N=16,mod=1e9+7; //表示剩余1个的颜色有i1个,剩余2个的颜色有i2个....有i5个,且当前位置已经放置了last颜色的方案数 int f[N][N][N][N][N][6]; int a[N]; int n; LL dp(int i1,int i2,int i3,int i4,int i5,int last){ //以后一个位置放什么个数的颜色来作为分类 if(f[i1][i2][i3][i4][i5][last])return f[i1][i2][i3][i4][i5][last]; LL res=0; if(i1)res=(res+dp(i1-1,i2,i3,i4,i5,1)*(i1-(last==2))%mod)%mod; if(i2)res=(res+dp(i1+1,i2-1,i3,i4,i5,2)*(i2-(last==3))%mod)%mod; if(i3)res=(res+dp(i1,i2+1,i3-1,i4,i5,3)*(i3-(last==4))%mod)%mod; if(i4)res=(res+dp(i1,i2,i3+1,i4-1,i5,4)*(i4-(last==5))%mod)%mod; if(i5)res=(res+dp(i1,i2,i3,i4+1,i5-1,5)*(i5)%mod)%mod; return f[i1][i2][i3][i4][i5][last]=res; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; a[x]++; } for(int i=1;i<=5;i++)f[0][0][0][0][0][i]=1; cout<<dp(a[1],a[2],a[3],a[4],a[5],0)<<endl; return 0; }
这题比赛时想的是单调栈,没搞出来,题解使用了st表,貌似出现了几次了这种情况,所以st表和单调栈(还有单调队列)可以绑定起来,想到一个的时候可以去试试另一个。
对于环,我们可以使用2种方法,分类讨论和断环为链。
一个区间内,一旦一个端点被固定下之后,这个区间内的最大值会随着区间的扩大而非严格单调递增,这具有单调性,所以我们可以使用二分来做。
同时为了维护区间最大值,可以使用st表。
教训:st表的1不要写成了i,debug一早上。。。
st表做法
#include<bits/stdc++.h> using namespace std; #define endl '\n' typedef long long LL; typedef pair<int,int> PII; const int INF=0x3f3f3f3f; const int N=3e5+10,M=19; int f[N][M]; int a[N],b[N]; int n; void init(){ for(int j=0;1<<j<n*3;j++){ for(int i=1;i+(1<<j)-1<=n*3;i++){ if(!j)f[i][j]=a[i]; else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]); } } } int query(int l,int r){ int t=31-__builtin_clz(r-l+1); return max(f[l][t],f[r-(1<<t)+1][t]); } bool check(int len,int i){ if(max(query(i-len,i-1),query(i+1,i+len))>=b[i])return true; return false; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; a[i]=a[i+n]=a[i+n+n]=x; } for(int i=1;i<=n;i++){ int x; cin>>x; b[i]=b[i+n]=b[i+n+n]=x; } init(); for(int i=1;i<=n;i++){ int l=1,r=n; while(l<r){ int mid=l+r>>1; if(check(mid,i+n))r=mid; else l=mid+1; } if(l==n)l=-1; cout<<l<<' '; } return 0; }
单调栈做法
之前没做出来就是不会断环为链。
#include<bits/stdc++.h> using namespace std; #define endl '\n' typedef long long LL; typedef pair<int,int> PII; const int INF=0x3f3f3f3f; const int N=3e5+10,M=19; int a[N],b[N],ans[N]; int stk[N],tt;//维护a的值 int n; int B_search(int x){ int l=1,r=tt; while(l<r){ int mid=l+r+1>>1; if(a[stk[mid]]>=x)l=mid; else r=mid-1; } return (a[stk[l]]>=x?l:-1); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n; memset(ans,0x3f,sizeof ans); for(int i=1;i<=n;i++){ int x; cin>>x; a[i]=a[i+n]=a[i+n+n]=x; } for(int i=1;i<=n;i++){ int x; cin>>x; b[i]=b[i+n]=b[i+n+n]=x; } for(int i=1;i<=n;i++){ while(tt&&a[stk[tt]]<=a[i])tt--; stk[++tt]=i; } for(int i=n+1;i<=2*n;i++){ int t=B_search(b[i]); if(~t){ ans[i-n]=min(ans[i-n],i-stk[t]); } while(tt&&a[stk[tt]]<=a[i])tt--; stk[++tt]=i; } tt=0; for(int i=3*n;i>=2*n+1;i--){ while(tt&&a[stk[tt]]<=a[i])tt--; stk[++tt]=i; } for(int i=2*n;i>=n+1;i--){ int t=B_search(b[i]); if(~t){ ans[i-n]=min(ans[i-n],stk[t]-i); } while(tt&&a[stk[tt]]<=a[i])tt--; stk[++tt]=i; } for(int i=1;i<=n;i++){ if(ans[i]<n)cout<<ans[i]<<' '; else cout<<-1<<' '; } return 0; }
D.P2879 [USACO07JAN] Tallest Cow S
算竞原题。
差分。
暴力即可。
F.P3420 [POI2005]SKA-Piggy Banks
并查集,再看有几个连通块。
比赛时困扰我的情况不会出现,因为一个点的祖先不会有2个,每个存钱罐只有一把钥匙。
简单组合数学。
收获:快速幂时,如果a大于p记得取模,要不然可能会爆LL。
H.P2910 [USACO08OPEN]Clear And Present Danger S
阅读理解+floyd板子
标签:4.11,int,res,i2,i5,i1,训练赛,hut21,mod From: https://www.cnblogs.com/F-beginner/p/17307899.html