套题 1

我真的，，这套题我只得了20分，痛定思痛定思痛定思痛定思痛定思痛定思痛定思痛定思痛定思痛定思痛定思痛定思痛。

t1 AcWing 145. 超市(贪心) （poj1456）

题目描述：超市里有N件商品，每个商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品（即当天di<=0）不能再卖。

　　求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

input：输入包含多组测试用例。每组测试用例，以输入整数N开始，接下里输入N对pi和，分别代表第i件商品的利润和过期时间。

　　在输入中，数据之间可以自由穿插任意个空格或空行，输入至文件结尾时终止输入，保证数据正确。

output：对于每组产品，输出一个该组的最大收益值。每个结果占一行。

例：4  50 2  10 1   20 2   30 1
　　7  20 1   2 1   10 3  100 2   8 2  5 20  50 10
输出：80
　　　185

0≤N≤10000
1≤pi,di≤10000


吐槽：拿到此题时我知道从开始当天过期中取最大直接贪心肯定错，然后我就把它倒了过来进行了这个过程。我还觉得我是对的嘤嘤嘤。
　　我把多组数据看成单组数据测试了。。。
题解：这个题可以卖出的最大数量其实是已经确定了的，就是有同一天过期不同价值的需要确定。
这样的话，不如从第一天开始先把遇到的能卖的都算进去，后来遇见能卖的但名额不够时就对此时已经确定的里面拿一个最小价值的，替换掉它。
到最后手中的那一些件的总价值即为答案。

#include <iostream> 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n,ans;
struct llo{
    int a,b;
} e[10003];
priority_queue <int> q;
bool cmp(llo x,llo y){
    return x.b<y.b;
}
int main(){
    //freopen("supermarket.in","r",stdin);
    //freopen("supermarket.out","w",stdout); 
    while(scanf("%lld",&n)==1){
        ans=0;
        for(int i=1;i<=n;i++)
            scanf("%d%d",&e[i].a,&e[i].b);
        sort(e+1,e+n+1,cmp);
        for(int i=1;i<=n;i++){
            if(e[i].b>q.size())    q.push(-e[i].a);
            else if(e[i].a>-q.top()){
                q.pop();
                q.push(-e[i].a);
            }
        }
        while(!q.empty())    ans+=(-q.top()),q.pop();
        printf("%lld
",ans);        
    }
    return 0;
}

View Code

题外：多组数据的输入scanf（)==1;
当没有数输入时，scanf返回-1，cin返回0

t2　AcWing 138.兔子与兔子

很久很久以前，森林里住着一群兔子。

有一天，兔子们想要研究自己的 DNA 序列。

我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。

然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。

注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。

输入格式

第一行输入一个 DNA 字符串 S。

第二行一个数字 m，表示 m 次询问。

接下来 m 行，每行四个数字

输出格式

对于每次询问，输出一行表示结果。

如果两只兔子完全相同输出 Yes，否则输出 No（注意大小写）。

数据范围

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int p,len,n;
long long b[1000003],f[1000003];
char s1[1000003]; 
int main(){
    cin>>(s1+1);
    p=103;
    b[0]=1;
    len=strlen(s1+1);
    for(int i=1;i<=len;i++){
        f[i]=f[i-1]*p+s1[i]-'a'+1;
        b[i]=b[i-1]*p;
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(f[r1]-f[l1-1]*b[r1-l1+1]==f[r2]-f[l2-1]*b[r2-l2+1])
            printf("Yes
");
        else printf("No
");
    }
    
    return 0;
}

View Code

t3 AcWing 272. 最长公共上升子序列

题目描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。
小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

输入描述 Input Description

第一行N，表示A，B的长度。
第二行，串A。
第三行，串B。

输出描述 Output Description

输出长度。

样例输入 Sample Input

4
2 2 1 3
2 1 2 3

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1<=N<=3000，A，B中的数字不超过maxlongint

论读题的重要性，我一直觉得它是让求最长公共子序列，并且纠结了好久为什么我的最长公共子序列没有打对。。。。。三道题看错两道，死了死了。
既然这样的话，这道题就非常地模板了。
我们让f【j】表示在b【j】中以j结尾，在a【1~n】中的最大公共上升子序列。
因为if(a[i]==b[j])    f[j]=max(f[j],maxn+1);，所以在从前往后循环中if(a[i]>b[j]&&maxn<f[j])    maxn=f[j];每次f【j】会被更新为截止到目前的i，以j结尾的最值。所以当a[i]>b[j]时继承的是i-1的最长，
为了等到a[i]==b[j]继承长度。

#include <iostream>
#include <cstdio>
using namespace std;
long long a[3002],b[3002];
int n,maxn,f[3002];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)    scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)    scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++){
        maxn=0;
        for(int j=1;j<=n;j++){
            if(a[i]>b[j]&&maxn<f[j])    maxn=f[j];
            if(a[i]==b[j])    f[j]=max(f[j],maxn+1);
        }
    }
    for(int i=1;i<=n;i++)
        maxn=max(maxn,f[i]);
    printf("%d",maxn);
    return 0;
}

View Code

这套题就此结束了，我真的是太太太马虎了，嘤。

套题 1

t1 AcWing 145. 超市(贪心) （poj1456）

t2 AcWing 138.兔子与兔子

输入格式

输出格式

数据范围

t3 AcWing 272. 最长公共上升子序列

t2　AcWing 138.兔子与兔子