题目链接: http://codevs.cn/problem/1068/

题意: 中文题诶~

思路: dp

用 dp[i][j][k][l] 表示取 i 个 1, j 个 2, k 个 3, l 个 4 时最大贡献为多少, 那么初始化为 dp[0][0][0][0] = v[1], 其中 v[i] 表示 i 这点的权值. 动态转移方程式为:

 int dis = i +  * j +  * k +  * l + ;
if(i) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - ][j][k][l] + v[dis]);
if(j) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - ][k][l] + v[dis]);
if(k) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - ][l] + v[dis]);
if(l) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - ] + v[dis]);

那么答案为 dp[a[1]][a[2]][a[3]][a[4]] 其中 a[i] 为 i 的数目.

代码:

 #include <iostream>
using namespace std; const int MAXN = ;
int dp[][][][], a[], v[MAXN]; int main(void){
int n, m, x;
cin >> n >> m;
for(int i = ; i <= n; i++){
cin >> v[i];
}
for(int i = ; i <= m; i++){
cin >> x;
a[x]++;
}
dp[][][][] = v[];
for(int i = ; i <= a[]; i++){
for(int j = ; j <= a[]; j++){
for(int k = ; k <= a[]; k++){
for(int l = ; l <= a[]; l++){
int dis = i + * j + * k + * l + ;
if(i) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - ][j][k][l] + v[dis]);
if(j) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - ][k][l] + v[dis]);
if(k) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - ][l] + v[dis]);
if(l) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - ] + v[dis]);
}
}
}
}
cout << dp[a[]][a[]][a[]][a[]] << endl;
return ;
}

最新文章

  1. ACM/ICPC 之 最小割转网络流(POJ3469)
  2. 实现如下类之间的继承关系,并编写Music类来测试这些类。
  3. UnWind Segue
  4. 点击事件touches与ios的手势UIGestureRecognizer
  5. pouchdb 安装使用
  6. flex安装时停在计算时间界面的解决办法
  7. Sublime Text生成html标签快捷键
  8. margin collapse 之父子关系的DIV
  9. CSS3中更灵活的布局方式
  10. 实现js浮点数加、减、乘、除的精确计算(网上很多文章里的方法是不能解决所有js浮点数计算误差的)
  11. AC自动机总结及板子(不带指针)
  12. Oracle触发bug(cursor: mutex S),造成数据库服务器CPU接近100%
  13. android客户端向服务器发送请求中文乱码的问
  14. eShopOnContainers 看微服务⑤:消息通信
  15. [PDFBox]后台操作pdf的工具类
  16. 剑指offer错题记录
  17. 对类方法进行约束(类的抽象方法ABC+raise抛出异常 )
  18. Redis 安装、配置、集群
  19. CoreSight™ Technology
  20. POJ-1644 To Bet or Not To Bet(概率DP)

热门文章

  1. HDU1272(并查集判图连通)
  2. Mybatis-Spring包学习
  3. Java基础--反射Reflection
  4. javaScript之NodeList
  5. 理解和正确使用Java中的断言(assert)
  6. eclipse 中使用 GreenUML 和 AmasterasUML 自动生成类图
  7. re.findall(?: ) ?:取消优先获取组的权限
  8. solr安装部署、solr测试创建core、用solrj 访问solr(索引和搜索)
  9. 爬取google的搜索结果并保存
  10. Codeforces 1097F Alex and a TV Show (莫比乌斯反演)