hdu 1421 1159 1087 容易dp

hdu 1421

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <stack>
#include <set>
#include <map>
#include <vector>

using namespace std;
#define INF 0x2fffffff
#define LL long long
#define MAX(a,b) ((a)>(b))?(a):(b)
#define MIN(a,b) ((a)<(b))?(a):(b)
int a[2005];
int dp[2005][10005];

int main(){
    int n,m;
    while(cin >> n >> m){

        for(int i = 1;i <= n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1);

        for(int i = 0;i <= m;i++){
            dp[0][i] = INF;
            dp[1][i] = INF; 
        }
        for(int i = 0;i <= n;i++){
            dp[i][0] = 0;
        }
        for(int i = 2;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(i < 2*j){
                    dp[i][j] = INF;
                }   
                else{
                    dp[i][j] = min(dp[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]),dp[i-1][j]);
                }
            }
        }
        printf("%d\n",dp[n][m]);
    } 
    return 0;
}

hdu 1159

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <stack>
#include <set>
#include <map>
#include <vector>

using namespace std;
#define INF 0x2fffffff
#define LL long long
#define MAX(a,b) ((a)>(b))?(a):(b)
#define MIN(a,b) ((a)<(b))?(a):(b)
char a[1005];
char b[1005];
int dp[1005][1005];

int main(){
    while(scanf("%s %s",a+1,b+1)!=EOF){
        int len1 = strlen(a+1);
        int len2 = strlen(b+1);
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){
                if(a[i] == b[j]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        printf("%d\n",dp[len1][len2]);
    }     
    return 0;
}

hdu 1087

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <stack>
#include <set>
#include <map>
#include <vector>

using namespace std;
#define INF 0x2fffffff
#define LL long long
#define MAX(a,b) ((a)>(b))?(a):(b)
#define MIN(a,b) ((a)<(b))?(a):(b)
int a[1005];
LL dp[1005];

int main(){
    int t;
    while(cin >>t ,t){
        for(int i = 0;i < t;i++){
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof(dp));
        dp[0] = a[0];
        LL  ans = a[0];
        for(int i = 0;i < t;i++){
            dp[i] = a[i];
            for(int j = 0;j < i;j++){
                if(a[i] > a[j]){
                    dp[i] = MAX(dp[i],dp[j]+a[i]);
                }
            }
            ans = MAX(dp[i],ans);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}