2017百度之星资格赛 1003:度度熊与邪恶大魔王(…
2018-06-17 22:08:45来源:未知 阅读 ()
度度熊与邪恶大魔王
1 /* 2 ans[i][j][b]表示防御力为b的怪物 3 表示用前i种技能,造成恰好j的伤害消耗的最小晶石 4 ans[i][j][b]=min{ans[i-1][j-x*(p[i]-b)]+x*k[i]} 5 x表示第i种技能取x个(0<=x*(p[i]-b)<=j) 6 优化:http://blog.csdn.net/wumuzi520/article/details/7014830 7 ans[i][j][b]=min(ans[i-1][j][b],ans[i][j-(p[i]-b)][b]+k[i]【j>=p[i]-b】) 8 =>ans[j][b]=min(ans[j][b],ans[j-(p[i]-b)][b]+k[i] **i从小到大 9 */ 10 #include<cstdio> 11 #include<cstring> 12 #include<algorithm> 13 using namespace std; 14 typedef long long LL; 15 LL n,m; 16 LL maxb,maxp,bx,maxa; 17 LL a[100100],b[100100]; 18 LL ans[10001][11]; 19 LL k[1010],p[1010],ans1; 20 int main() 21 { 22 LL i,j,t,ze=(long long)0; 23 while(scanf("%lld%lld",&n,&m)==2) 24 { 25 maxb=0;maxp=0;maxa=0; 26 for(i=1;i<=n;i++) 27 { 28 scanf("%lld%lld",&a[i],&b[i]); 29 maxb=max(maxb,b[i]); 30 maxa=max(maxa,a[i]); 31 } 32 for(i=1;i<=m;i++) 33 { 34 scanf("%lld%lld",&k[i],&p[i]); 35 maxp=max(maxp,p[i]); 36 } 37 maxa=max(maxa,maxp); 38 /* 39 去掉以上这句,会让类似 40 1 1 41 45 10 42 4164 327 43 的数据得出错误结果 44 */ 45 if(maxb>=maxp) 46 { 47 printf("-1\n"); 48 continue; 49 } 50 memset(ans,0x3f,sizeof(ans)); 51 memset(ans[0],0,sizeof(ans[0])); 52 for(bx=0;bx<=maxb;bx++) 53 { 54 for(i=1;i<=m;i++) 55 for(j=max(ze,p[i]-bx);j<=2*maxa;j++) 56 // { 57 //if(j>=p[i]-bx) 58 ans[j][bx]=min(ans[j][bx],ans[j-p[i]+bx][bx]+k[i]); 59 // } 60 t=0x3f3f3f3f; 61 for(j=2*maxa;j>=0;j--) 62 { 63 t=min(t,ans[j][bx]); 64 ans[j][bx]=min(ans[j][bx],t); 65 } 66 } 67 ans1=0; 68 for(i=1;i<=n;i++) 69 ans1+=ans[a[i]][b[i]]; 70 printf("%lld\n",ans1); 71 72 73 } 74 return 0; 75 }
题解:2017百度之星资格赛 1003:度度熊与邪恶大魔王(DP)
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:命名管道跨进程通讯
- windows7 + Qt(MSVC2017) + VS2019安装配置 2020-04-25
- 2020年04月10日UCF Local Programming Contest 2017 2020-04-10
- Qt最新版5.12.2在Win10环境静态编译安装和部署的完整过程(VS 2019-08-29
- 番茄助手 最新 Visual Assist X 适应于VS2019 VS2017 VS2015 2019-08-16
- 递归(七):递归程序填空 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash