1.16 dp总结
thomas1234567 · · 个人记录
dp总结
总分： 163 //第一题没换行
- 0
- 40
- 20
- 10
- 100
- 0
第一题 B2064 斐波那契数列
1.代码：错误
#include<bits/stdc++.h>
#define int long long
int dp[100005];
using namespace std;
void node(){
int x;
cin>>x;
for(int i=1;i<=x;i++){
if(i==1){
dp[i]=1;
continue;
}
if(i==2){
dp[i]=1;
continue;
}
dp[i]=dp[i-1]+dp[i-2];
}
cout<<dp[x]；//写错了，没换行
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
node();
}
}代码：正确
#include<bits/stdc++.h>
#define int long long
int dp[100005];
using namespace std;
void node(){
int x;
cin>>x;
for(int i=1;i<=x;i++){
if(i==1){
dp[i]=1;
continue;
}
if(i==2){
dp[i]=1;
continue;
}
dp[i]=dp[i-1]+dp[i-2];
}
cout<<dp[x]<<endl;
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
node();
}
}2.四步法：
1.确定状态
dp[i]斐波那契数列的i列
2.确定答案
dp[n]
3.确定状态转移方程
dp[i]=dp[i-1]+dp[i-2]
4.确定初始值和边界条件
dp[i]=1
第二题 P5732 【深基5.习7】杨辉三角
1.代码：正确
#include<bits/stdc++.h>
#define int long long
int dp[50][50];
using namespace std;
signed main(){
int n;
cin>>n;
dp[1][1]=1;
cout<<dp[1][1]<<endl;
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=dp[i-1][j]+dp[i - 1][j-1];
cout << dp[i][j] << ' ';
}
cout<<endl;
}
}2.四步法：
1.确定状态
dp[i][j] 以(i,j) 为最大答案
2.确定答案
max{dp[n][i]} n行的全部答案最大值
3.确定状态转移方程
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
4.确定初始值和边界条件
dp[1][1]=a[1][1]
第三题 B3637 最长上升子序列
1.代码：正确
#include<bits/stdc++.h>
#define int long long
int a[1000000];
int dp[1000000];
using namespace std;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int maxx=1;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<=i;j++){
if(a[i]>a[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
maxx=max(maxx,dp[i]);
}
cout<<maxx;
}2.四步法：
四步法： 1.确定状态
dp[i]以i结尾的最长上升子序列的长度
2.确定答案
max(maxx,dp[i])
3.确定状态转移方程
dp[i]=dp[i-1]+dp[i-2]
4.确定初始值和边界条件
dp[i]=1
第四题 P6702 [COCI2010-2011#7] ŠEĆER
1.代码：正确
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n;
cin>>n;
int minn=1e9;
int flag=0;
for(int i=0;i<=5000;i++){
for(int j=0;j<=5000;j++){
if(i*3+j*5==n){
minn=min(i+j,minn);
flag=1;
}
}
}
if(flag==1){
cout<<minn;
}
else{
cout<<-1;
}
}四步法：
1.确定状态
dp[i]i颗糖的最少盒子数
2.确定答案
dp[n]
3.确定状态转移方程
dp[i]=min(dp[i-3]+dp[i-5])+1 i-3是加1个3颗糖的盒子
i-5是加1个5颗糖的盒子
4.确定初始值和边界条件
dp[0]=0 dp[1]=dp[2]=dp[4]=1e9
第五题 P1028 [NOIP2001 普及组] 数的计算
1.代码：正确
#include<bits/stdc++.h>
#define int long long
int dp[100005];
using namespace std;
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<=i/2;j++){
dp[i]+=dp[j];
}
}
cout<<dp[n];
}2.四步法：
1.确定状态
dp[i]
2.确定答案
dp[n]
3.确定状态转移方程
p[i]+=dp[j];
4.确定初始值和边界条件
dp[i]=1
第六题 P1057 [NOIP2008 普及组] 传球游戏
送头文件：
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#define tin int
#define itn int
#define tni int
#define nit int
#define nti int
#define pritnf printf
#define scnaf scanf
#define int long long
using namespace std ;
signed main()
{
// std::ios::sync_with_stdio( false ) ;
// std::cin.tie( 0 ) ;
// std::cout.tie( 0 ) ;
return 0 ;
}