传送门

Description

  Matrix67要在下个月交给老师n篇论文,论文的内容可以从m个课题中选择。由于课题数有限,Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说,对于某个课题i,若Matrix67计划一共写x篇论文,则完成该课题的论文总共需要花费Ai*x^Bi个单位时间(系数Ai和指数Bi均为正整数)。给定与每一个课题相对应的Ai和Bi的值,请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这n篇论文。

Input

  第一行有两个用空格隔开的正整数n和m,分别代表需要完成的论文数和可供选择的课题数。

  以下m行每行有两个用空格隔开的正整数。其中,第i行的两个数分别代表与第i个课题相对应的时间系数Ai和指数Bi。

Output

  输出完成n篇论文所需要耗费的最少时间。

Sample Input


Sample Output


Hint

对于30%的数据,n<=,m<=;

对于100%的数据,n<=,m<=,Ai<=,Bi<=。

Solution

  第一次定义的方程为f[i]表示写前i篇论文的最小花费,发现无法转移。因为a*(x+y)^b显然不等于a*x^b+a*y^b。考虑阶段划分:对于同一种课题的花费,在一个状态中要一次性计算下来,否则就会出现无法转移的情况。由此可将课题种类数作为阶段,设f[i][j]表示用前i个课题写j篇论文的花费。转移显然:f[i][j]=min{f[i-1][k]+a[i]*pow((j-k),b[i])|其中k<j}。显然可以把第一维滚动掉,但是我懒得滚了= =。

  对于边界,f[i][0]=0,其中i∈[0,m]

Code

#include<cstdio>
#include<cstring>
#define maxn 205
#define maxm 25
#define ll long long int inline void qr(ll &x) {
char ch=getchar();ll f=;
while(ch>''||ch<'') {
if(ch=='-') f=-;
ch=getchar();
}
while(ch>=''&&ch<='') x=(x<<)+(x<<)+(ch^),ch=getchar();
x*=f;
return;
} inline ll max(ll a,ll b) {return a>b?a:b;}
inline ll min(ll a,ll b) {return a<b?a:b;} inline void swap(ll &a,ll &b) {
ll c=a;a=b;b=c;return;
} ll n,m,frog[maxn][maxn]; struct Pa {
ll a,b;
};
Pa pa[maxn]; ll pow(ll a,ll b) {
if(!b) return ;
if(!(b^)) return a;
ll t=b/;
ll an=pow(a,t);
if(b%) return an*an*a;
else return an*an;
} int main() {
qr(n);qr(m);
for(int i=;i<=m;++i) {
qr(pa[i].a);qr(pa[i].b);
}
std::memset(frog,0x3f,sizeof frog);frog[][]=;
for(int i=;i<=m;++i) frog[i][]=;
for(int i=;i<=m;++i) {
for(int j=;j<=n;++j) {
for(int k=;k<=j;++k) {
frog[i][j]=min(frog[i][j],frog[i-][j-k]+pa[i].a*pow(k,pa[i].b));
}
}
}
printf("%lld\n",frog[m][n]);
return ;
}

Summary

1、不要闲的没事一上来就压维。发现状态不对容易懵逼

2、在设计状态的时候,一般而言需要在一个状态中需要一次性计算的会被作为阶段进行划分,划分时注意感性领悟一下无后效性原则,不要闷头方程。

3、在不压维状态下若以一个维度为阶段无法转移可以尝试使用另一个维度作为阶段

4、对于看起来需要记录以往信息但又明显不是状压的DP(例如本题若使用论文数作为阶段需要记录对于每一个状态每一个课题选了多少),一般而言会把需要记录的信息作为阶段,目的还是,方便一次性计算。

5、初始化的时候把所有能想到的边界全部初始化掉。别嫌麻烦。不然容易GG。

End on 2018/6/3

最新文章

  1. JS函数无响应
  2. iOS resign code with App Store profile and post to AppStore
  3. VPN fq工具的选择
  4. Vnc viewer与windows之间的复制粘贴
  5. [zz]论程序员
  6. apache使用ssl数字证书
  7. httperf ---linux web站点压力测试
  8. MySQL索引和优化查询
  9. vs未找到导入的项目,请确认 &lt;Import&gt; 声明中的路径正确
  10. Ubuntu在下面LAMP(Linux+Apache+MySQL+PHP) 开发环境的搭建
  11. 企业建站http://www.douco.com/
  12. 用python抓取求职网站信息
  13. Why you should QC your reads AND your assembly?
  14. issubclass判断前面是不是后面的子类
  15. PHP 5 MySQLi 函数
  16. 《java入门第一季》之集合框架TreeSet存储元素自然排序以及图解
  17. if语句&amp;switch&amp;Scanner
  18. XML文档的简易增删查改
  19. 关于java使用POI导出ppt ,其中表格setText 失败问题
  20. grep 笔记

热门文章

  1. wordlist 4
  2. C if语句判断年龄
  3. js for循环实例
  4. Python爬虫模拟登录带验证码网站
  5. typescript 学习记录
  6. Java中String类
  7. HDU 3262/POJ 3829 Seat taking up is tough(模拟+搜索)(2009 Asia Ningbo Regional)
  8. nodejs笔记--Events篇(二)
  9. java日期格式处理
  10. Python 循环语句和运算符