动态规划(入门,滚动数组,记录的都是状态):SWUSTACM-1010 魔兽争霸之最后的反击
题目:
1010: 魔兽争霸之最后的反击
Time Limit: 1000 MS Memory Limit: 65536 KB
Description
相传人族与兽族对峙了很久,双方均受到了重创,兽族趁人类没有能力发起大规模进攻之时突然袭击,想一次彻底打败人族。人类为了生存,无论老幼伤病,全部参战,兵分两路抗敌。
由于体质不同,我们以血量表示一个人的战斗力,现在给你所有人的血量,请你把人类分成战斗力最接近的两部分。注意,战斗力要最接近,不然,人族会因你而战败呦!
Input
第一行为一个整数n(1<=n<=36),表示人族的总人数。以下的n行每行一个整数,表示一个人的血量mi(即战斗力),其中1<=mi<=400.
Output
只有一行,包含两个数,即人族的每部分兵的血量总和,较小的一个值放在前面,两个数用空格分隔。
Sample Input
3
20
32
35
Sample Output
35 52
Source
SWUST
解题心得:
1、可以直接价将最大的战斗值/2,然后动态规划就行了。在规划的过程中状态有几种转移的方法。注意此题记录的都是状态(只有false和true),因为记录的是状态所以开的数组直接是bool类型就可以了,第一维是记录的物品的个数,第二维记录的是在选择第k个物品(人族的群数)的时候有多少种可能的重量(战斗力)。当可以达到这个重量的时候将这个重量记录为true。
第一种:
就是很简单的记录人群的数量和总的战斗力,直接给代码.
关于核心的动态规划解释一下:第k件物品,可以选择不装入,所以选择第k件物品的重量就是和第k-1个相同物品的状态相同。也可以选择装入,装入就必须第前一个状态【k-1】的 j-t[j] 要是true才可以转移到这个状态。
#include<bits/stdc++.h>
using namespace std;
bool dp[40][16000];//只是记录的状态bool就可以了,甚至bitset也可以;
int t[40];
int main()
{
int n;
int sum ;
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
sum = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
sum += t[i];
}
dp[0][0] = 1;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=0;j--)
{
for(int k=1;k<=n;k++)
dp[k][j] = dp[k-1][j] | dp[k-1][j-t[k]];//这个是核心算法
}
}
for(int i=sum/2;i>=0;i--)
{
if(dp[n][i])
{
printf("%d %d\n",i,sum-i);
break;
}
}
}
}
#include<bits/stdc++.h>
using namespace std;
bool dp[2][16000];
int t[40];
int main()
{
int n;
int sum ;
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
sum = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
sum += t[i];
}
dp[0][0] = 1;
int now;
for(int i=1;i<=n;i++)
{
for(int j=sum;j>=0;j--)
{
if(j >= t[i])
dp[i%2][j] = dp[(i+1)%2][j] | dp[(i+1)%2][j-t[i]];
else
{
if(dp[(i+1)%2][j])
dp[i%2][j] = 1;
}
}
now = i;//用来记录最后的那个数组,写的好弱智;
}
for(int i=sum/2;i>=0;i--)
{
if(dp[now%2][i])
{
printf("%d %d\n",i,sum-i);
break;
}
}
}
}
第三种:开一个一维数组直接转移就可以了
其实思想也很简单,这个状态转移不是从前面一次到后面转移,而是从后面往前面转移,所以后面的状态不会影响前面的状态,直接转移就可以了。
#include<bits/stdc++.h>
using namespace std;
bool dp[16000];
int t[40];
int main()
{
int n;
int sum ;
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
sum = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
sum += t[i];
}
dp[0] = 1;
for(int i=1;i<=n;i++)
for(int j=sum;j>=0;j--)
{
dp[j] = dp[j] | dp[j-t[i]];
}
for(int i=sum/2;i>=0;i--)
{
if(dp[i])
{
printf("%d %d\n",i,sum-i);
break;
}
}
}
}
最新文章
- 463. Island Perimeter
- 30 GroupSock(Port)——live555源码阅读(四)网络
- [知识点]Trie树和AC自动机
- UIImageJPEGRepresentation和UIImagePNGRepresentation
- Git Shell 安装版本
- 在IIS7.5打开网页的时候,提示: HTTP 错误 500.0 - Internal Server Error 调用 LoadLibraryEx 失败,在 ISAPI 筛选器 ";C:\Windows\Microsoft.NET\Framework\v4.0.30319\\aspnet_filter.dll"; 上。解决方法
- Android(java)学习笔记167:Java中操作文件的类介绍(File + IO流)
- ERROR<;53761>; - Plugins - conn=-1 op=-1 msgId=-1 - Connection Bind through PTA failed (91). Retrying...
- MarkDown/reST 文档发布流水线
- 用分治法解决最近点对问题:python实现
- 201521123013 《Java程序设计》第7周学习总结
- 《算法导论》学习总结 — XX.第22章 图的基本算法
- JS基本数据类型(typeof的返回结果)
- i春秋----Misc
- CentOS下MySQL的安装
- python之路(9)反射、包装类、动态模块导入
- @deprecated 的方法处理
- MogoDB(6)--mongoDB高可用和4.0特性
- Qsys 设计流程---Qsys System Design Tutorial
- 在Unity场景中控制日夜的轮转