Codeforces 1307 E Cow and Treats —

Codeforces 1307 E Cow and Treats —— 想法

本文主要是介绍Codeforces 1307 E Cow and Treats —— 想法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

现在有一行，每格都有草，每个草的甜度为ai，现在有m头牛，每头牛喜欢的甜度和要吃的格数都告诉你，现在你要安排这些牛去吃草，每头牛只能从左到右或从右到左吃，它吃饱了之后就会停下来，并且之后的牛不能再通过这个格子，并且吃过的草不会再长出来。问你最多有多少牛可以吃饱并且在此前提下有多少种方法。

题解：

这种问你情况的题目并不要求让你输出具体怎么做，有时候我就会从怎么将它做出来考虑，那样就不容易做出来，其实这道题目很简单。因为奶牛吃完了之后就不允许其它奶牛通过，所以一个方向吃相同草的奶牛最多只有一个，然后另外一个方向有可能也有一个。这样我们就分每种草考虑左边以及右边的个数。
我们枚举从左往右最远的牛的位置，然后再枚举草的种类，这时候有一些情况：如果当前草的种类和最远的草的种类相同的话，说明这种情况左边只有一种，也就是我们枚举到的最远的牛（自己理解一下），右边的情况如果右边的草的数量>=左边的草的数量就-1因为这头牛被安排了，然后还有一些情况。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e3+5;
const ll mod=1e9+7;
int a[N];
vector<int>vec[N];
int l[N],r[N];
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int x,y;for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),vec[x].push_back(y);for(int i=1;i<=n;i++)sort(vec[i].begin(),vec[i].end());ll a1=0,a2=0;for(int i=0;i<=n;i++){memset(l,0,sizeof(l));memset(r,0,sizeof(r));for(int j=1;j<=i;j++)l[a[j]]++;for(int j=i+1;j<=n;j++)r[a[j]]++;int f=i?0:1,mx=i?1:0;//f表示这次有没有正好会在第i次结束的奶牛ll s=1;//cout<<vec[a[i]].size()<<endl;for(auto j:vec[a[i]]){if(j==l[a[i]]){f=1;break;}}if(!f)continue;for(int j=1;j<=n;j++){int lef=0,rig=0;for(auto x:vec[j]){if(x>l[j])break;lef++;}for(auto x:vec[j]){if(x>r[j])break;rig++;}if(j==a[i])lef=0,rig-=r[j]>=l[j];if(!lef&&!rig)continue;if(lef>rig)swap(lef,rig);if(!lef)s=s*rig%mod,mx++;else if(rig==1)s=s*2%mod,mx++;elses=s*lef*(rig-1)%mod,mx+=2;}if(mx>a1)a1=mx,a2=s;else if(mx==a1)a2=(a2+s)%mod;}printf("%lld %lld\n",a1,a2);return 0;
}
/*
5 2
1 1 1 1 1
1 2
1 3*/