啊哈磊_编程从这里起步

标题: [dp]不是采药 [打印本页]

---

作者: 邀请码    时间: 2016-8-23 15:52
标题: [dp]不是采药

1. 
   
2. #include <stdio.h>
   
3. int max(int x,int y){return x>y?x:y;}
   
4. int main(){
   
5. &nbsp; &nbsp; int n,m,w[101],c[101],dp[1001]={0};
   
6. &nbsp; &nbsp; scanf("%d%d",&m,&n);
   
7. &nbsp; &nbsp; for(int i=1;i<=n;i++)
   
8. &nbsp; &nbsp; scanf("%d%d",c+i,w+i);
   
9. &nbsp; &nbsp; for(int i=1;i<=n;i++)
   
10. &nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp;for(int j=c[i];j<=n;j++)
    
11. &nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp; &nbsp;dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
    
12. &nbsp; &nbsp; printf("%d\n",dp[m]);
    
13. &nbsp; &nbsp; return 0;
    
14. }
    

复制代码

---

作者: 邀请码    时间: 2016-8-23 15:53
卧槽哪里来的那么多&nbsp;

---

作者: 邀请码    时间: 2016-8-23 15:54

1. 
   
2. 
   
3. #include <stdio.h>
   
4. int max(int x,int y){return x>y?x:y;}
   
5. int main(){
   
6.     int n,m,w[101],c[101],dp[1001]={0};
   
7.     scanf("%d%d",&m,&n);
   
8.     for(int i=1;i<=n;i++)
   
9.     scanf("%d%d",c+i,w+i);
   
10.     for(int i=1;i<=n;i++)
    
11.         for(int j=c[i];j<=n;j++)
    
12.             dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
    
13.     printf("%d\n",dp[m]);
    
14.     return 0;
    
15. }
    

复制代码

---

欢迎光临 啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)

Powered by Discuz! X3.2