队列得分

题解：

考察点： 动态规划，分类讨论

易错点：

题目中指出，而又是取自队列的，因此假设当前位于队列当中的位置，则之前的任何位置都可能成为其在中的上一个位置

解法一：动态规划

设表示在队列中位置的最大值，表示元素个数的最小值。根据在易错点中的分析之前的任意一个位置都可能成为新队列中位置的上一个位置，因此由所有比它小的位置和的作用转移过来，也即是。同时由于位于后面的位置一定不可能得到在元素更少的情况下拥有和前面位置相同的值，因此直接由转移过来就好了，时间复杂度为

#include "bits/stdc++.h"
using namespace std;
const int maxn=500+10;
struct node{
    int Set,Value;
}p[maxn];
int n,dp[maxn],num[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&p[i].Set,&p[i].Value);
    }
    int mx=0,mxnum=0;
    for(int i=1;i<=n;i++){
        int tmp=0,cur=0;
        for(int j=1;j<i;j++){
            if(tmp<dp[j]-(p[i].Set==p[j].Set?10:0)){
                tmp=dp[j]-(p[i].Set==p[j].Set?10:0);
                cur=num[j];
            }
        }
        dp[i]=tmp+p[i].Value;
        num[i]=cur+1;
        if(mx<dp[i]){
            mx=dp[i];
            mxnum=num[i];
        }
    }
    printf("%d %d\n",mx,mxnum);
    return 0;
}

解法二：分类讨论

认真分析题目，不难发现，对于选取的队列中连续且相同元素具有如下性质：

如果这一段里面的所有元素都小于等于，则只能从中选出个元素，否则会起反作用，因此毫无疑问应该选取值最大的那个

如果这一段中存在大于的，则只选取所有大于的部分，并统计个数

基于上述性质，只需分类讨论每个位置和的关系，同时对于连续且相同的元素，看作一个合在一起处理，对于内的元素应用性质和性质进行分类讨论即可，时间复杂度

#include "bits/stdc++.h"
using namespace std;
const int maxn=500+10;
struct node{
    int Set,Value;
}p[maxn];
int n;
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].Set,&p[i].Value);
    int i=1;
    int sum=0,num=0;
    while(i<=n){
        int pos=i;
        int cnt=0,sum10=0,ans=0;
        while(pos<=n&&p[pos].Set==p[i].Set){
            if(p[pos].Value<=10){
                ans=max(ans,p[pos].Value);
            }
            else{
                sum10+=p[pos].Value;
                cnt++;
            }
            pos++;
        }
        if(cnt>0){
            sum+=sum10-((cnt-1)*10);
            num+=cnt;
        }else{
            sum+=ans;
            num+=1;
        }
        i=pos;
    }
    printf("%d %d\n",sum,num);
    return 0;
}