BUY LOW, BUY LOWER, POJ - 1952(LIS+去重计数)

一开始疯狂WA,后来用别人题解代码debug发现
2
1 1
这组数据应该输出1,而我输出0,原来是ans初始化错了。。。。

解析:
我去重的思想是,如果a [ i ] == a [ j ] (j<i) && dp [ i ] == dp [j ] ,那么说明就存在重复序列了,为了避免之后算重复,则有:

(f为计数数组,储存的是长度为dp[ i ]且以a [ i ] 结尾的 对应的不重复序列数
f [ i ] -= f [ j ](好像f [ i ] = 0也是一个道理),这样后面更新时,就只会加一个 f [ j ], 不会重复,因为之前的重复的被减掉了;

而如果 dp [ i ] 被更新了,则 f [ i ] = f [ j ] (dp [ i ] = dp [ j ] + 1 时),因为最长长度增加了,f [ i ] 就重置了(正如前面 f 数组的定义);

a[ i ] < a [ j ] 的情况就照常计数。

AC代码

#include<algorithm>
#include<cctype>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=5e3+5;
LL f[N],dp[N],a[N];
int main()
{
    int n;
    while(scanf("%lld",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i] );

        LL ans1=1,ans2=1;///初始化
        dp[1]=f[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=f[i]=1;
            for(int j=1;j<i;j++)
            {
                if(a[i]<a[j])
                {
                    if(dp[i]<dp[j]+1)///重置
                    {
                        dp[i]=dp[j]+1;
                        f[i]=f[j];
                    }
                    else if(dp[i]==dp[j]+1) ///计数
                        f[i]+=f[j];
                }
                else if(a[i]==a[j]&&dp[i]==dp[j])///去重
                    f[i]-=f[j];
            }
            ///算答案
            if(ans1<dp[i])///重置答案
            {
                ans1=dp[i];
                ans2=f[i];
            }
            else if(ans1==dp[i])///计数
                ans2+=f[i];
        }

        printf("%lld %lld\n",ans1,ans2);

    }
    return 0;
}

如果有什么没有明白的,可以模拟一下代码运行,或者再下面提问也可以的。

上一篇:[mysql8]新坑哈 更改Mysql 表的大小转换设置lower_case_table_names=1


下一篇:model_state = state.models[app_label, self.name_lower]