题意： 给出一根棍子的长度，以及n个需要切割的点，每一次切割的代价是这一段需要被切割的长度 问代价最小时的代价值 题解： 区间dp dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[j]-a[i]); i 为区间左端点，j 为右端点，k为中间的子问题 dp表示某一个区间的最小切割值 区间dp 的思路，先枚举区间大小，然后枚举区间的起始位

题意： 见刘汝佳入门书籍 P275 dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*a[i].c+a[i].k);题解： 见刘汝佳入门书籍 P275 #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int dp[1010]

题意： 给你 t 秒时间，有n首歌，每一首歌的时间不超过三分钟，在结束之前唱一首678秒的劲歌金曲 选了一首歌就一定要唱完 并且在保持唱的歌曲数量最多的情况下，时间最长 题解： 虽然 t 的范围很大，有十的九次方，但是n最多只有50 ，所以不会总时间超过 180*50+678 秒 此时就可以用01背包了，但是有两个最优条件 用结构体存，并且重载小于符合，设置优先级，见代码

题意： 给定一个n*m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的 题解： 动态规划 每一列是一个阶段，一个阶段有三个决策，逆推可以方便的记录路径然后顺着打印出来 字典序最小很巧妙的利用排序解决了 需要注意的是m==1的情况，所以下面的双 if  不能用 if  else if

题意： 给出按照 x 坐标排序的一系列二维坐标上的点，让你通过来回走一圈，把所有点都恰好走一遍，除了最左端和最右端的点 使得总路程最短 题解： 让两个人同时走，并且不重合，从左边开始走道右边去 令dp【i】【j】表示两个人分别走道  i  和走到  j 的时候的最短路 因为dp【i】【j】==dp【j】【i】 故强行令  i > j 然后dp【i】【j】可以转移到dp【i+1

题意： 给出不超过30个立方体，每一种有无穷多个。 要求这些立方体堆成一个尽量搞的柱子，使得每一个立方体下面的立方体的底面长宽都大于上面的底面长宽 题解： 很明显我们可以将每个立方体当做3个或者6个不一样的不可以旋转的长方体 下面代码当做6个，是为了方便计算，这样在判断的过程中不需要加太多条件 而且数据量不大，可以这样做 dp思想： 01背包的思想，放与不放，最后求一

lrj 入门经典  p267 从本题得到的收获： 分清主线： 影响决策的只有时间以及所处的车站 理清次线： 火车跑来跑去的，我们需要处理好他们，为我们的主线服务，即，在某些车站的时候，是否有车在这个时间 故令 dp【】【】，第一维表示时刻，第二维表示在某车站出发，需要等待的时间 写dp就要注意：初始化条件： 这里的初始化条件就是dp【T】【i】为INF，但是在终