T1：
小喵喵有 n 个小鱼干排成一列，其中第 i个小鱼干有两种属性，美味度 ai 和特殊度 bi
现在小喵喵要吃掉一些小鱼干，出于一些原因，小喵喵会吃掉连续的一段区间中的所有小鱼干。
如果吃掉了 [l,r]一段区间，那么小喵喵会获得一些满意度。
形式化地，总满意度 =(ai,l<=i<=r)×(1+bi,l<=i<=r)
由于只有小喵喵最喜欢的小鱼干的特殊度等于 11，所以 bi=1 的小鱼干数量不会超过 400个，其他的 bi=0
现在小喵喵可以选择任意一段区间（不能为空），但是有一些小鱼干的美味度是负数，吃掉所有小鱼干不一定会获得最多的满意度。所以小喵喵想知道最大能获得的总满意度是多少。
思路：
模拟+优化
首先可以想到n*n的模拟，但是复杂度过高于是我们想到：
可以在每个bi等于1的点预处理一个数组，表示这个点向左最大能延伸到多少
这样我们在枚举每个点的时候就只需要枚举在它之前有多少个bi为1的点就可以了
但是只是这样还是有问题的，如果最大值是不经过任何一个bi为1的点结果就是有问题的
所以我们需要再单独跑一遍判断
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<set> 8 #include<map> 9 #include<vector> 10 #include<stack> 11 #include<queue> 12 #define ll long long 13 #define inf 2147383611 14 #define MAXN 101010 15 #define MOD 16 using namespace std; 17 inline ll read() 18 { 19 ll x=0,f=1; 20 char ch;ch=getchar(); 21 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 22 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 23 return x*f; 24 } 25 ll n,a[MAXN],k[MAXN],cnt,sa[MAXN],b[MAXN],ans,m[MAXN],x; 26 int main() 27 { 28 n=read(); 29 for(int i=1;i<=n;i++) {a[i]=read();sa[i]=sa[i-1]+a[i];} 30 for(int i=1;i<=n;i++) {x=read();b[i]=b[i-1]+x;if(x) k[++cnt]=i;} 31 k[0]=0,k[cnt+1]=n+1; 32 //for(int i=1;i<=cnt+1;i++) cout<<i<<" "<<k[i]<<endl; 33 ll tmp,_max; 34 memset(m,-127,sizeof(m)); 35 for(int i=1;i<=cnt;i++) 36 { 37 tmp=0,_max=a[k[i]]; 38 for(int j=k[i];j>k[i-1];j--) 39 { 40 tmp+=a[j]; 41 if(tmp>=_max) {m[i]=j;_max=tmp;} 42 } 43 } 44 //for(int i=1;i<=cnt;i++) cout<<m[i]<<endl; 45 ll res; 46 if(b[1]) ans=sa[1]*b[1]; 47 else ans=sa[1]; 48 for(int i=1;i<=n;i++) 49 { 50 if(b[i]) ans=max(ans,sa[i]*b[i]); 51 else ans=max(sa[i],ans); 52 for(int j=b[i];j>=1;j--) 53 { 54 ans=max(ans,(sa[i]-sa[m[j]-1])*(b[i]-j+2)); 55 //cout<<i<<" "<<j<<" "<<(sa[i]-sa[k[j]-1])*(b[i]-j+2)<<endl; 56 } 57 } 58 for(int i=1;i<=cnt+1;i++) 59 { 60 tmp=-inf; 61 for(int j=k[i-1]+1;j<k[i];j++) 62 { 63 if(tmp<0&&a[j]<=0) tmp=max(tmp,a[j]); 64 if(tmp>=0) tmp+=a[j]; 65 if(tmp<0&&a[j]>0) tmp=a[j]; 66 ans=max(ans,tmp); 67 //cout<<i<<" "<<j<<" "<<tmp<<endl; 68 } 69 } 70 printf("%lld",ans); 71 }
T2：
绵羊送给小喵喵了 n 个小鱼干。小喵喵要把它们全部吃掉！
但是绵羊告诉小喵喵要按照某种顺序来吃。
绵羊一共说了 m 条限制，每条限制的格式为 u v，表示要先吃掉 u 号小鱼干之后才能吃 v 号小鱼干。
绵羊保证，这些条限制不会出现循环需求的情况，即一定存在某种顺序使得 n 个小鱼干都被吃掉。
绵羊还允许小喵喵不遵守其中小于等于 k 条限制。
小喵喵想知道在吃完所有的小鱼干的前提下，吃小鱼干的顺序的字典序最小是多少。
两个吃小鱼干的顺序的字典序大小比较即为：首先比较第一个吃的小鱼干，编号较小的字典序较小，若相同，则比较第二个吃的小鱼干，一直比到可以分出大小。
注意到两个顺序一定可以比较大小
思路：
几乎是裸的拓扑排序
只需要记录一下他的入度，判断它的入度是否小于k
即是否可以加到队列前面
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<set> 8 #include<map> 9 #include<vector> 10 #include<stack> 11 #include<queue> 12 #define ll long long 13 #define inf 2147383611 14 #define MAXN 152701 15 #define MOD 16 using namespace std; 17 inline ll read() 18 { 19 ll x=0,f=1; 20 char ch;ch=getchar(); 21 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 22 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 23 return x*f; 24 } 25 int cnt,n,m,k,to[MAXN],first[MAXN],next[MAXN],in[MAXN]; 26 priority_queue <int,vector<int>,greater<int> > q; 27 bool vis[MAXN],out[MAXN]; 28 void add(int u,int v) {in[v]++,next[++cnt]=first[u],first[u]=cnt,to[cnt]=v;} 29 int main() 30 { 31 n=read(),m=read(),k=read(); 32 int a,b; 33 while(m--) {a=read(),b=read();add(a,b);} 34 for(int i=1;i<=n;i++) 35 if(in[i]<=k) {q.push(i);vis[i]=1;} 36 int pos,t; 37 while(!q.empty()) 38 { 39 pos=q.top(); 40 q.pop(); 41 vis[pos]=0; 42 if(in[pos]>k) continue; 43 printf("%d ",pos); 44 k-=in[pos],out[pos]=1; 45 for(int i=first[pos];i;i=next[i]) 46 { 47 t=to[i]; 48 if(out[t]) continue; 49 in[t]--; 50 if(!vis[t]&&in[t]<=k) {q.push(t);vis[t]=1;} 51 } 52 } 53 }