成品网站 代理,制作图片文字模板的软件,阳江网站制作公司,沈阳网页排名优化方法正题
题目链接:http://noip.ybtoj.com.cn/contest/90/problem/3 解题思路
有nnn道题#xff0c;mmm个人。一些题目是让某些人一定得分#xff0c;一些题目是让某些人可以能得分。
求排名前sss的人选出ttt个人#xff0c;可能的集合个数。 解题思路
显然我们如果要判断一…正题
题目链接:http://noip.ybtoj.com.cn/contest/90/problem/3 解题思路
有nnn道题mmm个人。一些题目是让某些人一定得分一些题目是让某些人可以能得分。
求排名前sss的人选出ttt个人可能的集合个数。 解题思路
显然我们如果要判断一个集合UUU能否被选择那么肯定是这个集合内的人选最高分其他的最低分。
那我们可以按照最高分数值从大到小排序然后枚举一个iii表示选择这个iii且这个iii后面的都不选择。那么这个iii肯定是这ttt个人里排名最后的那么我们要从iii前面选t−1t-1t−1个然后要求大于iii的最大值的分数不到sss个考虑dpdpdp这个iii前面的选择方案。
设fi,j,kf_{i,j,k}fi,j,k表示选到第iii个现在选择了jjj个大于maximax_imaxi的没有选择的minminmin值有kkk个的方案。
时间复杂度O(n4)O(n^4)O(n4) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N55;
ll n,m,s,t,ans,a[N],mx[N],mi[N],p[N],f[N][N][N];
char str[N];
bool cmp(ll x,ll y)
{return mx[x]mx[y];}
int main()
{freopen(ctsc.in,r,stdin);freopen(ctsc.out,w,stdout);scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);scanf(%lld,m);for(ll i1;im;i){scanf(%s,str1);for(ll j1;jn;j){if(a[j]0)mx[i]-a[j]*(str[j]Y);else mx[i]a[j]*(str[j]Y),mi[i]a[j]*(str[j]Y);}mx[i]100*mx[i]m-i;mi[i]100*mi[i]m-i;p[i]i;}scanf(%lld%lld,s,t);sort(p1,p1m,cmp);for(ll i1;im;i){ll ks-t;for(ll ji1;jm;j)if(mx[p[i]]mi[p[j]])k--;memset(f,0,sizeof(f));f[0][0][0]1;for(ll j1;ji;j)for(ll h0;ht;h)for(ll g0;gk;g){//f[j][h][g]表示选到第i个现在选了h个有g个比它大 if(gmi[p[j]]mx[p[i]])f[j][h][g]f[j-1][h][g-1];else if(mi[p[j]]mx[p[i]]) f[j][h][g]f[j-1][h][g];if(h)f[j][h][g]f[j-1][h-1][g];}for(ll g0;gk;g)ansf[i-1][t-1][g];}printf(%lld,ans);return 0;
}
