重庆集训DAY13

T1 假签。赛时想到了n^2的DP，也不知道是假了还是哪里打错了，只有20分（该死的多测，过了大多数点但很多被卡了）。正解是n^3的，但很多人的程序跑得比标程快。所以n^2的做法是存在的（调不出来）。虽然没过但我还是把错误代码放一下。

//0||100
#include<bits/stdc++.h>
using namespace std;
int dp[400][400],f[400][400],n,k,l,r;
string a;
int main()
{
    freopen("beach.in","r",stdin);
    freopen("beach.out","w",stdout);
    cin>>n>>k;
    cin>>a;
    for(int i=a.size();i>=1;i--)
    {
        a[i]=a[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            l=0;
            r=0;
            if(a[j]==&#039;C&#039;)
            {
                l=1;
            }
            if(a[n-i+j]==&#039;C&#039;)
            {
                r=1;
            }
            if(i%2==1)
            {
                if(dp[i-1][j-1]+l<dp[i-1][j]+r)
                {
                    dp[i][j]=dp[i-1][j-1]+l;
                    f[i][j]=f[i-1][j-1];
                }
                else
                if(dp[i-1][j-1]+l==dp[i-1][j]+r)
                {
                    if(f[i-1][j-1]>f[i-1][j])
                    {
                        dp[i][j]=dp[i-1][j-1]+l;
                        f[i][j]=f[i-1][j-1];
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j-1]+r;
                        f[i][j]=f[i-1][j];
                    }
                }
                else
                {
                    dp[i][j]=dp[i-1][j]+r;
                    f[i][j]=f[i-1][j];
                }
            }
            else
            {
                if(f[i-1][j-1]+l<f[i-1][j]+r)
                {
                    f[i][j]=f[i-1][j-1]+l;
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                if(f[i-1][j-1]+l==f[i-1][j]+r)
                {
                    if(dp[i-1][j-1]>dp[i-1][j])
                    {
                        f[i][j]=f[i-1][j-1]+l;
                        dp[i][j]=dp[i-1][j-1];
                    }
                    else
                    {
                        f[i][j]=f[i-1][j-1]+r;
                        dp[i][j]=dp[i-1][j];
                    }
                }
                else
                {
                    f[i][j]=f[i-1][j]+r;
                    dp[i][j]=dp[i-1][j];
                }
            }
//          cout<<i<<"  "<<j<<"  "<<f[i][j]<<"        "<<dp[i][j]<<endl;
            if(f[i][j]>=k)
            {
                cout<<"DA"<<endl;
                return 0;
            }
            if(dp[i][j]>=k)
            {
                cout<<"NE"<<endl;
                return 0;
            }           
        }
    }
    cout<<"NE"<<endl;
}

T2 数学。。。赛时打了50的暴力但是不知道为什么大家的暴力都只有20.赛后用数学方法转换式子，借用快速幂和预处理阶乘搞掉。（谁赛时能想到用这种办法解决啊！