学步园

看完题就想用DP做，再看discuss才意识到这题根本没那么麻烦

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int t;
    int n,m;
    int a;
    scanf("%d",&t);
    while(t--){
        int minn=105;
        scanf("%d%d",&n,&m);
        while(n--){
            scanf("%d",&a);
            if(a<minn) minn=a;
        }
        printf("%d\n",(100-minn)*(100-minn));
    }
    return 0;
}

不过还是用DP试了试，数据很小O(n4)水过。费用是最多可选择的课程数，另外再增加一维记录已经选定课程中最大的难度值

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int f[42][42][105];
int main(){
    int t,n,m;
    int i,j,k,kk;
    int a[50];    
    scanf("%d",&t);
    while(t--){
        int ans=0;
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        a[n]=100;
        sort(a,a+n+1);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(k=0;k<=n;k++){
                    for(kk=0;kk<k;kk++){
                        f[i][j][a[k]]=max(f[i][j][a[k]],f[i-1][j-1][a[kk]]+(a[k]-a[kk])*(a[k]-a[kk]));
                        if(f[i][j][a[k]]>ans)
                            ans=f[i][j][a[k]];
                    }
                }
        printf("%d\n",ans);
    }
    return 0;
}