dp

P1049 [NOIP 2001 普及组] 装箱问题 
#include <bits/stdc++.h>
#define V 20010
#define maxn 35
using namespace std;

int n, m;
int f[maxn][V], a[maxn];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
f[i][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if(j >= a[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - a[i]] + a[i]); 
else f[i][j] = f[i - 1][j];
cout << m - f[n][m] << endl;
    return 0;
}

P1048 [NOIP 2005 普及组] 采药   
#include "stdio.h"
#include "iostream"
using namespace std;
int w[105], val[105];
int dp[1005];
int main()
{
    int t,m,res=-1;    
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&val[i]);
    }
    for(int i=1;i<=m;i++) 
    {
        for(int j=t;j>=0;j--) 
        {
            if(j>=w[i])
            {
                dp[j]=max(dp[j-w[i]]+val[i], dp[j]);
            }
        }
    }    
    printf("%d",dp[t]);
    return 0;
}

P1060 [NOIP 2006 普及组] 开心的金明  
#include<iostream>
#include<algorithm>
using namespace std;
int w[30],v[30],f[50000];
int n,m;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        w[i]*=v[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            if(j>=v[i])
            {
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

P1063 [NOIP 2006 提高组] 能量项链         ##更改
#include<bits/stdc++.h>
using namespace std;
int n,e[300],s[300][300],maxn=-1;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){cin>>e[i];e[i+n]=e[i];}
    for(int i=2;i<2*n;i++){
        for(int j=i-1;i-j<n&&j>=1;j--){
            for(int k=j;k<i;k++)
            s[j][i]=max(s[j][i],s[j][k]+s[k+1][i]+e[j]*e[k+1]*e[i+1]);
            if(s[j][i]>maxn)maxn=s[j][i];
        }
    } 
    cout<<maxn;
    return 0;
}