syhd142  
日历
<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910
统计
  • 随笔 - 23
  • 文章 - 122
  • 评论 - 31
  • 引用 - 0

导航

常用链接

留言簿(2)

随笔档案(23)

文章分类(270)

文章档案(122)

我的豆瓣

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
类似背包问题,对NO2有15种状态,在每个状态有使用和不使用两种情况,分别考虑。特别注意在状态14时,即2哥NO2+80%能量,要单独判断
所以状态方程很容易就出来了,具体见代码。
#include 
<stdio.h>
//using namespace std;

#define N 105
#define E 15
#define INF 1 << 28

int main()
{
    
//freopen("in", "r", stdin);
    int n, l;
    
int a[N], b[N], e[2][E];
    
while(~scanf("%d %d"&n, &l))
    {
        
for(int i = 0; i < n; i++)
            scanf(
"%d"&a[i]);
        
        
for(int i = 0; i < n; i++)
            scanf(
"%d"&b[i]);
        
        e[
0][0= 0;
        
for(int i = 1; i < E; i++)
        {
            e[
0][i] = INF;
        }
        
        
for(int k = 0; k < l; k++)
        {
            
for(int i = 0; i < n; i++)
            {
                e[
1][0= INF;
                
for(int j = 0; j < E; j++)
                {
                    e[
1][j + 1= e[0][j] + a[i];
                    
if(j > 4 && e[0][j] + b[i] < e[1][j - 5])
                    {
                        e[
1][j - 5= e[0][j] + b[i];
                    }
                }
                
if(e[0][E - 1+ b[i] < e[1][E - 6])
                {
                    e[
1][E - 6= e[0][E - 1+ b[i];
                }
                
if(e[0][E - 1+ a[i] < e[1][E - 5])
                {
                    e[
1][E - 5= e[0][E - 1+ a[i];
                }
                
for(int j = 0; j < E; j++)
                {
                    e[
0][j] = e[1][j];
                }
            }
        }
        
int ans = INF;
        
for(int i = 0; i < E; i++)
        {
            
if(e[0][i] < ans) ans = e[0][i];
        }
        printf(
"%d\n", ans);
    }
    
return 0;
}
posted on 2010-09-09 23:58 Fucker 阅读(598) 评论(3)  编辑 收藏 引用 所属分类: ACM/ICPCDP
评论:

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Fucker Powered by: 博客园 模板提供:沪江博客