随笔 - 6, 文章 - 5, 评论 - 0, 引用 - 0
数据加载中……

rqnoj[2]开心的金明

很简单的一题,但是对DP很不熟悉,这好像也是第一次自己写dp的题目,写下错误吧。
#include <stdio.h>
int main()
{
    long n,m,i,j,a[30001]={0},v[26],w[26];
    
    scanf("%ld%ld",&n,&m);
    for(i=0;i<m;i++)
    scanf("%ld%ld",&v[i],&w[i]);
   
    for(i=0;i<m;i++)
        for(j=n;j>=v[i];j--)
            if(a[j-v[i]]+v[i]*w[i]>a[j])a[j]=a[j-v[i]]+v[i]*w[i];
            
    printf("%ld",a[n]);
    
    return 0;
}
很基础的一题,但是在开始对n和m的含义弄混了,导致无输出。
后来在for(j=n;j>=v[i];j--)
中判断条件设成了j>0   没用弄清具体含义,下次要注意。
           

posted on 2011-11-02 21:32 slytherin 阅读(273) 评论(0)  编辑 收藏 引用


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