BestCoder——59

http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=640

第一题：给一堆书的序列 每次操作只能将书从中间移到最上面 求最少移动多少次 使得有序

只有19本书 

怎么暴力怎么来

可以观察出 一本书最多被移动一次 不然移动就不存在意义了

ID最大的书是不被移动的 so 倒着查询有多少本是不被移动的就行了

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;


int a[50];
int main()
{
    int Cas;
    scanf("%d",&Cas);
    while (Cas--)
    {
        int n;
        scanf("%d",&n);
        for (int i = 1;i<=n;i++)
        scanf("%d",&a[i]);
        for (int i = n;i>=1;i--)
        {
            if (a[i] == n)
                n--;
        }
        printf("%d
",n);
    }
    return 0;
}

第二题：求最多的分数

sum = a[i] - b[i]*(耗费的时间)

贪心 加 搜索 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
const int maxn = 10000 + 100;
struct node{
    int a,b,c;
}p[maxn];

bool cmp(node t1,node t2)
{
    return (LL)t1.c*t2.b < (LL)t2.c*t1.b;
}
int dp[maxn];
int main()
{
    int Cas;
    scanf("%d",&Cas);
    while (Cas--)
    {
        int n,t;
        scanf("%d%d",&n,&t);
        for (int i = 1;i<=n;i++)
        {
            scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
            
        }
        sort(p+1,p+n+1,cmp);
        
        
        memset(dp,0,sizeof(dp));
        for (int i = 1;i<=n;i++)
        {
            for (int j = t;j>=p[i].c;j--)
            {
                dp[j] = max(dp[j],dp[j-p[i].c] + (p[i].a - p[i].b * j));
            }
        }
        int ans = 0;
        for(int i = 0; i <= t; i++) ans = max(ans, dp[i]);
        printf("%d
", ans);
        
    }
    return 0;
}

第四题： 判断一个得分序列是否有效

https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Score_sequences_and_score_sets

代码是看别人的 以后就直接用了（以后应该也没有这种题了）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
using namespace std;

#define maxn 50005
int n,x[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&x[i]);
        sort(x,x+n);
        int sum1=0;
        int sum2=0;
        bool sign=1;
        for(int i=0;i<n;i++)
        {
            sum1+=x[i];
            sum2+=i;
            if(sum1<sum2) sign=0;
        }
        if(sum1!=sum2) sign=0;
        if(sign) puts("It seems to have no problem.");
        else puts("The data have been tampered with!");
    }
}