HIT暑期集训 动态规划

A    CodeForces 1150D

C    Gym 102056I

E    CodeForces 1120C

官方题解

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 5005
using namespace std;
int f[maxn][maxn],dp[maxn];
char s[maxn];
int main()
{
    int i,j,k,n,a,b;
    scanf("%d%d%d%s",&n,&a,&b,s+1);
    for (i=1;i<=n;i++)
    for (j=i;j<=n;j++)
        if (s[i]==s[j]) f[i][j]=f[i-1][j-1]+1;
    for (i=1;i<=n;i++) dp[i]=a*n;
    dp[0]=0;
    for (i=1;i<=n;i++) 
    {
        dp[i]=dp[i-1]+a;
        for (j=1;j<i;j++)
        {
            k=min(i-j,f[j][i]);
            if (k) dp[i]=min(dp[i],dp[i-k]+b);
        }
    }
    printf("%d
",dp[n]);
    return 0;
}

F    CodeForces 1110D

题解参考

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 1000005
using namespace std;
int dp[maxn][3][3],cnt[maxn],a[maxn],n,m;
int main()
{
    int i,j,k,t,lim;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0][0]=0; 
    for (i=0;i<=m+1;i++)
    for (j=0;j<3;j++)
    for (k=0;k<3;k++)
    {
        if (dp[i][j][k]<0) continue;
        lim=cnt[i+1]-j-k;
        for (t=0;t<3 && t<=lim;t++)
            dp[i+1][k][t]=max(dp[i+1][k][t],dp[i][j][k]+(lim-t)/3+t);
    }
    printf("%d
",dp[m+1][0][0]);
    return 0;
}