省选题Orz

#include<cstring>
#include<set>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
set<string>a,b;
int main(){
    int n,ans,i,j;char c;string s;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        cin>>s;
        transform(s.begin(),s.end(),s.begin(),::tolower);
        a.insert(s);
    }
    s.clear();
    while(~scanf("%c",&c)){
        c=tolower(c);
        if(c>='a'&&c<='z')s.push_back(c);
        else{
            if(!s.empty()){
                if(a.find(s)!=a.end())b.insert(s);
                s.clear();
            }
            if(c=='.'){
                ans+=b.size();
                b.clear();
            }
        }
    }
    printf("%d",ans);
    return 0;
}

然后WA了QAQ

终于AC啦,Orz出题人......

姬妹,I love you!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 838ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 478ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1419ms

考虑下答案性质，可以将情敌分为三部分，一部分没有，一部分在第一月，一部分在第二月，接下来可以证明将情敌分为三部分且每部分时间总和不超过上限的方案是可行方案，所以DP下即可。

注意要INT64

把树形动归转化成线性的

具体的参看---|何森

我发现我的算比较快的了，虽然是笨办法。。。

把情敌排序（未被保护的特殊情敌，后面是每个超级情敌跟着它的小弟），然后做背包，未被保护的部分直接做。后面的由于超级情敌最多只有4个，而每个超级情敌所保护的小弟可能非常多，所以不能枚举灭了每个超级情敌后小弟怎么灭，而是要枚举每个超级情敌（不灭，第一个月灭，第二个月灭），然后多次做它们小弟部分的背包。。。

笨办法，大家见笑了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：103ms

f[i][j][k]记录第一个月前i天，第二个月前j天的最大值。k的第i位为1表示第i个超级情敌是要消灭的，为0表示第i个超级情敌不消灭。

代码在：

此题阴险毒辣，所有记录答案的变量都要设成int64.否则第9个点会挂。切记！切记！

AC 100题

庆祝一下

Flag 　　Accepted

题号 　　P1628

类型(?) 　　动态规划

通过 　　17人

提交 　　73次

通过率 　　23%

难度 　　2

大概f的动规吧~~

[ls都是神牛~]

题目很不好，数据很弱~

m太小了~

要我出复杂度和m无关的才好~

0ms...

地下室

用longint第9个点错了，改成int64 就过了。

……

测试数据 #0: Accepted, time = 0 ms, mem = 5304 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5308 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 5304 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5304 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 5304 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 5304 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 5304 KiB, score = 10
测试数据 #7: Accepted, time = 234 ms, mem = 5308 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 5308 KiB, score = 10
测试数据 #9: Accepted, time = 125 ms, mem = 5300 KiB, score = 10
Accepted, time = 466 ms, mem = 5308 KiB, score = 100

五十分的多半是写二维了QWQ

详细题解请来访：

http://hi.baidu.com/samroxas/item/360c5ecb2b5c1b2946d5c09f

先枚举超级情敌的消灭情况

在做二维背包

Accepted 有效得分：100 有效耗时：903ms

最裸的方法，好难看的时间……

第一次郁闷的90，去下了数据，才知道有一个测试点总代价要int64=.=

改了int64速度就更慢了……

纪念，第100人AC！

Accepted 有效得分：100 有效耗时：0ms

终于卡在前100人了,,,真希望我交的那刹那有人先我ac一下下,,这样就能正好100人了,,,,,

哪位大COW发个标程来KK啊