我的NOIP2010就杯具在这道题上了，多么简单啊！考完回来坐在那立刻就想起来了！
唉……杯具的省二等！这道题拿下不就省一了么。
直到保送之后、直到今天，我才能静下心来AC这道题。
以下是我的代码：
#include<iostream>
using namespace std;
const int kMaxn (351),kMaxc (41);
int max(int a,int b){return (a>b?a:b);}
int d[kMaxc][kMaxc][kMaxc][kMaxc];
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int n,m,r[kMaxn],cards_count[5]={0};
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>r[i];
for(int i=1;i<=m;i++)
{
int t;
cin>>t;
cards_count[t]++;
}
for(int i=0;i<=cards_count[1];i++)
for(int j=0;j<=cards_count[2];j++)
for(int k=0;k<=cards_count[3];k++)
for(int l=0;l<=cards_count[4];l++)
{
d[i][j][k][l]=r[1];
int now=1+i+2*j+3*k+4*l;
if(i>=1)
d[i][j][k][l]=max(d[i][j][k][l],d[i-1][j][k][l]+r[now]);
if(j>=1)
d[i][j][k][l]=max(d[i][j][k][l],d[i][j-1][k][l]+r[now]);
if(k>=1)
d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k-1][l]+r[now]);
if(l>=1)
d[i][j][k][l]=max(d[i][j][k][l],d[i][j][k][l-1]+r[now]);
}
cout<<d[cards_count[1]][cards_count[2]][cards_count[3]][cards_count[4]]<<endl;
return 0;
}
posted on 2011-03-08 12:00
lee1r 阅读(1033)
评论(2) 编辑 收藏 引用 所属分类:
题目分类：动态规划