✪线性dp✪

P1095 [NOIP2007 普及组] 守望者的逃离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

先算出只用一种方式走，枚举1~T的时间

dp[i]代表第i秒走出的距离

再算另一种，如果这一秒以另一种方式走来走的更远，那么我们就更新这个距离，在每1秒，只需要考虑在前一步能走出的最大距离上，这一步以什么方式走来更快，所以这样是能保证无后效性的

规规矩矩的DP:

#include
using namespace std;


int M;	//魔法初值
int S;	//距离
int T;	//沉没时间 

int dp[300005]; 

int main(){
	cin>>M>>S>>T;
	//先计算一直用魔法的 
	for(int i=1;i<=T;i++){
		if(M>=10){
			dp[i]=dp[i-1]+60;
			M-=10;
		}
		else{
			dp[i]=dp[i-1];
			M+=4;
		}
	}
	//如果在这一s用跑步走得更远，就用跑步替换 
	for(int i=1;i<=T;i++){
		dp[i]=max(dp[i],dp[i-1]+17);
		//如果到了 
		if(dp[i]>=S){
			cout<<"Yes"< 
 
甚至可以不创建数组且只用一次循环，这个是，魔法走更远那么就替换跑步
 
 
 
#include
using namespace std;


int M;	//魔法初值
int S;	//距离
int T;	//沉没时间 


int main(){
	cin>>M>>S>>T;
	int s1=0,s2=0;	//跑步能走的距离和闪烁能走的距离
	for(int i=1;i<=T;i++){
		s1+=17;
		if(M>=10){
			s2+=60;
			M-=10;
		}
		else
			M+=4;
		//如果闪更快，就替换跑的
		if(s2>=s1)s1=s2;
		if(s1>S){
			//成功逃离
			cout<<"Yes"< 
 
 
P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 
 
 
 
把题意简化：
 
 
​
 
 
我们想求dp[n][m]，那么就把所有的都算出来
 
 
 
 
DP的核心其实是从上一层的最优解推下一层的最优解
 
 
用dp[i][j]代表前i种花摆m盆的方案数 
 
 
 PS.洛谷的第一篇题解类比了很多种方法，特别好！！
 
 
 
#include
using namespace std;

int m;	//m盆 
int n;  //n种 
int a[105];	//第i种不超过多少盆 
int dp[105][105];	//dp[i][j]代表前i种花摆m盆的方案数 

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=min(j,a[i]);k++)//k代表的是第i种花选了几盆 
				dp[i][j]=(dp[i][j]+dp[i-1][j-k])%1000007;
		}
	} 
	cout< 
 
P3842 [TJOI2007]线段 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 
 
 
 
 
 
 
 
#include
using namespace std;
int n,a[20001][2],f[20001][2];//a[i][0]表示l[i],a[i][1]表示r[i]
int dis(int a,int b)//计算距离
{
	return abs(a-b);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i][0],&a[i][1]);
	f[1][0]=dis(a[1][1],1)+dis(a[1][1],a[1][0]);
	f[1][1]=dis(a[1][1],1);
	for(int i=2;i<=n;i++)//状态转移
	{
		f[i][0]=min(f[i-1][0]+dis(a[i-1][0],a[i][1])+dis(a[i][1],a[i][0]),f[i-1][1]+dis(a[i-1][1],a[i][1])+dis(a[i][1],a[i][0]))+1;
		f[i][1]=min(f[i-1][0]+dis(a[i-1][0],a[i][0])+dis(a[i][0],a[i][1]),f[i-1][1]+dis(a[i-1][1],a[i][0])+dis(a[i][0],a[i][1]))+1;
	}
	printf("%d",min(f[n][0]+dis(a[n][0],n),f[n][1]+dis(a[n][1],n)));//最后的答案还要加上到(n,n)的距离
}