Metal Steak

Hard to eat

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  0 Posts :: 79 Stories :: 0 Comments :: 0 Trackbacks

公告

aaaaaaaaaaaa

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

#include <iostream>
using namespace std;

int
n, m, t, cost[
1002], f[1002], g[1002];

void
__read__()
{
    cin 
>> n >> m >> t;
    
forint i = 1; i <= n; i++ )
        cin 
>> cost[i];
}

void
__init__()                       
//这个init有点不好理解
{
    f[
0= 0;
    g[
0= 9999999;
    
forint i = 1; i <= n; i++ )
        f[i] 
= 9999999;
}

void
__dp__()
{
    
forint i = 1; i <= n; i++ )
        
forint j = i; j > 0; j-- )
            
if( g[j - 1+ cost[i] > t )
            {
                
if( f[j - 1+ 1 < f[j] )
                {
                    f[j] 
= f[j - 1+ 1;
                    g[j] 
= cost[i];
                }
                
if( f[j - 1+ 1 == f[j] )
                    
if( g[j] > cost[i] )
                        g[j] 
= cost[i];
            }
            
else
            {
                
if( f[j - 1< f[j] )
                {
                    f[j] 
= f[j - 1];
                    g[j] 
= g[j - 1+ cost[i];
                }
                
if( f[j - 1== f[j] )
                    
if( g[j] > g[j - 1+ cost[i] )
                        g[j] 
= g[j - 1+ cost[i];
            }
}

void
__outp__()
{
    
forint i = n; i > 0; i-- )
        
if( f[i] <= m )
        {
            cout 
<< i << endl;
            
return;
        }
}

int
main()
{
    __read__();
    __init__();
    __dp__();
    __outp__();

    
return 0;
}

posted on 2009-09-15 20:55 mad4alcohol 阅读(43) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理