C与C++ 算法笔记中的代码
生活随笔
收集整理的這篇文章主要介紹了
C与C++ 算法笔记中的代码
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
EOF使用：
MAC系統：輸入結束后需要—>回車鍵—>(control+D)。即可結束輸入。
windows系統：輸入結束后需要—>回車鍵—>(control+Z)—>回車鍵
C++ 這里的 = 拷貝是值拷貝，會得到一個新的數組
class Solution { public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// C++ 這里的 = 拷貝是值拷貝，會得到一個新的數組auto matrix_new = matrix;for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {matrix_new[j][n - i - 1] = matrix[i][j];}}// 這里也是值拷貝matrix = matrix_new;} };begin()函數和end()位于iteartor；
而front()和back()位于vector list deque and etc…
C++ 標準模版庫STL
除開vector和string之外的STL容器都不支持*(it+i)的訪問方式
vector:向量/變長數組
set:集合 內部自動有序且不含重復元素
#include<set> using namespace std; 定義：set<int> name; 訪問：迭代器 set<int>::iterator it;通過*it來訪問set里的元素 函數：insert()find(value) 返回set中對應值為value的迭代器erase()size()clear()string字符串:
#include<string> using namespace std; 定義： string str; 訪問：下標：str[i]如果要讀入和輸出整個字符串，則只能用cin和cout迭代器： string::iterator it; 函數：operator+=str1+=str2; //將str2直接拼接到str1上length()/size()insert()erase()clear()substr()string::npos:-1find()replace()map映射：map會以鍵從小到大的順序自動排序，map的鍵和值是唯一的
#include<map> using namespace std; 定義：map<string,int> mp; 訪問：下標：mp['c']迭代器 map<char,int>::iterator it;通過 it->first 來訪問鍵 it->second來訪問值 函數：find(key) 返回鍵為key的映射的迭代器erase()size()clear()queue 隊列：
#include<queue> using namespace std; queue<int> q; push() pop() front() back() empty() size()priority_queue 優先隊列：隊首元素優先級最大
#include<queue> using namespace std; priority_queue<int> q; push() pop() top() empty() size() priority_queue<int,vector<int>,greater<int> >q; //最小的元素放在隊首 struct fruit{string name;int price;friend bool operator < (fruit f2,fruit f2){return f1.price > f2.price;} };stack 棧：
#include<stack> using namespace std; stack<int> st; push() pop() top() empty() size()pair 一個內部有兩個元素的結構體：
#include<utility> using namespace std;algorithm：
**sort(首元素地址，尾元素地址的下一個地址，cmp比較函數):** #include<algorithm> using namespace std; 在STL標準容器中，只有 vector向量、string字符串、deque隊列 是可以使用sort的 **#include <numeric>：** accumulate(a,b,c)累加求和： a為起始地址，b為結束地址，c為初始值 #include <numeric> vector<int> v={1,2,3,4}; int sum = accumulate(v.begin(),v.end(),0);C++和C：
C++中有string類型；len=str.length()
C語言中沒有單獨一種基本數據類型可以存儲字符串，只能使用字符數組的方式。（字符串常量可以作為初值賦給字符數組，并使用%s的格式輸出）;len=strlen(str)
char str[4]=“abcd”;
printf("%s",str);
C++可以直接使用布爾型；
C語言中必須添加stdbool.h頭文件才可以使用
C語言中不允許在for語句的表達式A里定義變量；
C++中可以
for(int i=1;i<=100;i++){
sum=sum+i;
}
C++：
引用：對引用變量的操作就是對原變量的操作(引用不是取地址)
void change(int &x){
x=1;
}
C：malloc free
C++：new delete
C++：
頭文件：
#include<stdio.h> #include（C++）
輸入：
scanf("%d",&n);
scanf("%lld",&n); //long long
scanf("%s",str);
scanf("%f",&f); //float
scanf("%lf",&db); //double
輸出：
printf("%d",n);
printf("%lld",n); //long long
printf("%f",fl); //float
printf("%f",db); //double
sscanf(str,"%d",&n)：把字符數組str中的內容以"%d"的格式寫到n中
sprintf(str,"%d",n)：把n以"%d"的格式寫到str字符數組中
%f是float和double型的輸出格式
轉義字符：\n \t \0
a^b：位異或
scanf("%s",str);
printf("%s",str);
getchar()：輸入單個字符，可以識別換行符
putchar()：輸出單個字符
gets()：輸入一行字符串
puts()：輸出一行字符串
注：
scanf輸入時：
%c格式能識別空格跟換行并將其輸入；
%s通過空格或換行來識別一個字符串的結束
gets()識別換行符\n作為輸入結束
注釋：/* */ 或 //
math函數
#include<math.h>
fabs(double x)：取絕對值
floor(double x)：向下取整
ceil(double x)：向上取整
pow(double x,double y)：x^y
sqrt(double x)：算術平方根
log(double x)：以自然對數e為底的對數
round(double x)：四舍五入，返回類型也是double型，需進行取整
const double pi=acos(-1.0);
#include<string.h>
memset(a,0,sizeof(a)); //賦值0或-1
strlen(str)：長度
strcmp()：返回兩個字符串大小的比較結果
strcpy()：復制
strcat()：連接
生成隨機數據：P144
[a,b]：rand()%(b-a+1)+a
[a,b],b>RAND_MAX：(int)round(1.0rand()/RAND_MAX(b-a)+a)
switch語句
switch(表達式){
case 常量表達式1:
……
break;
case 常量表達式n:
……
break;
default:
……
}
數組：
一維數組：
int a[10]={5,3,2,6,8,4};
int a[10]={} //都賦初值0
數組作為函數參數時：
參數中數組的第一維不需要填寫長度（如果是二維數組，那么第二維需要填寫長度），實際調用時也只需填寫數組名；
在函數中對數組元素的修改就等同于是對原數組元素的修改（這與普通的局部變量不同）P59
指針：
指針指向內存地址
只要在變量前面加上&，就表示變量的地址
指針變量用來存放指針
數組的名稱作為數組的首地址使用 a==&a[0]
a+i==&a[i] *(a+i)==a[i]
兩個int型的指針相減，等價于在求兩個指針之間相差了幾個int
結構體：
struct studentInfo{int id;char name[20];studentInfo *next; }stu,*p; //訪問變量 stu.id p->id #include<stdio.h> struct Point{int x,y;Point(){} //用以不經初始化地定義pt[10]Point(int _x,int _y):x(_x),y(_y){} //用以提供x和y的初始化 }pt[10];int main(){int num=0;for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){pt[num++]=Point(i,j); //直接使用構造函數}}for(int i=0;i<num;i++){printf("%d,%d\n",pt[i].x,pt[i].y);}return 0; }代碼實例
簡單：
//PAT B1032 挖掘機技術哪家強 P86 #include<stdio.h> const int maxn=100010; int school[maxn]={0}; int main(){int n,schID,score;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&schID,&score);school[schID]+=score;}int k=1,MAX=-1;for(int i=1;i<=n;i++){if(school[i]>MAX){MAX=school[i];k=i;}}printf("%d %d\n",k,MAX);return 0; }中等：
//冒泡排序 #include<stdio.h> int main(){int a[10]={3,1,4,5,2};for(int i=1;i<=4;i++){ //循環4次for(int j=0;j<5-i;j++){if(a[j]>a[j+1]){int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}for(int k=0;k<5;k++){printf("%d ",a[k]);}return 0; } //PAT B1020 月餅 P118 #include<stdio.h> #include<algorithm> using namespace std; struct mooncake{double store; //庫存量double sell; //總售價double price; //單價 }cake[1010]; bool cmp(mooncake a,mooncake b){ //按單價從高到低排序return a.price>b.price; } int main(){int n;double D;scanf("%d%lf",&n,&D);for(int i=0;i<n;i++){scanf("%lf",&cake[i].store);}for(int i=0;i<n;i++){scanf("%lf",&cake[i].sell);cake[i].price=cake[i].sell/cake[i].store; //計算單價}sort(cake,cake+n,cmp); //按單價從高到低排序double ans=0; //收益for(int i=0;i<n;i++){if(cake[i].store<=D){ //如果需求量高于月餅庫存量ans+=cake[i].sell;D-=cake[i].store;}else{ //如果月餅庫存量高于需求量ans+=D*cake[i].price;break;}}printf("%.2f\n",ans);return 0; } //PAT B1019/A1069 數字黑洞 P152 #include<stdio.h> #include<algorithm> using namespace std; bool cmp(int a,int b){return a>b; } void to_array(int n,int num[]){ //將n中每一位存到num數組中for(int i=0;i<4;i++){num[i]=n%10;n=n/10;} } int to_number(int num[]){ //將num數組轉換為數字int sum=0;for(int i=0;i<4;i++){sum=sum*10+num[i];}return sum; }int main(){int n,MIN,MAX; //MIN和MAX分別表示遞增排序和遞減排序后得到的最小值和最大值scanf("%d",&n);int num[5];while(1){to_array(n,num);sort(num,num+4);MIN=to_number(num);sort(num,num+4,cmp);MAX=to_number(num);n=MAX-MIN;printf("%04d-%04d=%04d\n",MAX,MIN,n);if(n==0 || n==6174) break; //退出}return 0; }復雜：
//日期差值P91 #include<stdio.h> int month[13][2]={ //平年和閏年的每個月的天數{0,0},{31,31},{28,29},{31,31},{30,30},{31,31},{30,30},{31,31},{31,31},{30,30},{31,31},{30,30},{31,31} }; bool isLeap(int year){ //判斷是否是閏年return (year%4==0 && year%100!=0) || (year%400==0); } int main(){int time1,y1,m1,d1;int time2,y2,m2,d2;while(scanf("%d%d",&time1,&time2)!=EOF){if(time1>time2){ //第一個日期晚于第二個日期，則交換int temp=time1;time1=time2;time2=temp;}y1=time1/10000,m1=time1%10000/100,d1=time1%100;y2=time2/10000,m2=time2%10000/100,d2=time2%100;int ans=1; //記錄結果//第一個日期沒有達到第二個日期時進行循環while(y1<y2||m1<m2||d1<d2){d1++;if(d1==month[m1][isLeap(y1)]+1){ //滿當月天數m1++;d1=1;}if(m1==13){ //月份滿12個月y1++;m1=1;}ans++;}printf("%d\n",ans);}return 0; } //PAT B1009 說反話 P97 #include<stdio.h> int main(){int num=0; //單詞的個數char ans[90][90];while(scanf("%s",ans[num])!=EOF){ //一直輸入直到文件末尾num++; //單詞個數加1}for(int i=num-1;i>=0;i--){ //倒著輸出單詞printf("%s",ans[i]);if(i>0) printf(" ");}return 0; }#include<iostream> #include<string> using namespace std; int main(){string str;getline(cin,str,'\n'); // char (*ans)[90]=(char(*)[90])malloc(sizeof(char)*90*90); // cin>>str;int len=str.length(),r=0,h=0; //r為行，h為列char ans[90][90]={}; //ans[0]~ans[r]存放單詞for(int i=0;i<len;i++){if(str[i]!=' '){ans[r][h++]=str[i];}else{ans[r][h]='\0';r++;h=0;}}for(int i=r;i>=0;i--){cout<<ans[i];if(i>0) printf(" ");}return 0; } //PAT A1025 Ranking P103 #include<stdio.h> #include<algorithm> using namespace std;struct Student{char id[15]; //準考證號int score;int location_number; //考場號int local_rank; //考場內排名 }stu[30010];bool cmp(Student a,Student b){if(a.score!=b.score) return a.score>b.score;else return strcmp(a.id,b.id)<0; }int main(){int n,k,num=0; //num為總考生數scanf("%d",&n); //n為考場數for(int i=1;i<=n;i++){scanf("%d",&k); //該考場內人數for(int j=0;j<k;j++){scanf("%s%d",stu[num].id,&stu[num].score);stu[num].location_number=i;num++;}sort(stu+num-k,stu+num,cmp); //將該考場的考生排序stu[num-k].local_rank=1;for(int j=num-k+1;j<num;j++){if(stu[j].score==stu[j-1].score){stu[j].local_rank=stu[j-1].local_rank;}else{stu[j].local_rank=j-num+k+1;}}}printf("%d\n",num); //輸出總考生數sort(stu,stu+num,cmp); //將所有考生排序int r=1;for(int i=0;i<num;i++){if(i>0 && stu[i].score!=stu[i-1].score){r=i+1; //當前考生與上一個考生分數不同時，讓r更新為人數+1}printf("%s %d %d %d\n",stu[i].id,r,stu[i].location_number,stu[i].local_rank);}return 0; } //輸出1～3的全排列 #include<stdio.h> const int maxn=11; //P為當前排列，hashTable記錄整數x是否已經在P中 int n,P[maxn],hashTable[maxn]={false}; //當前處理排列的第index號位 void generateP(int index){if(index==n+1){ //遞歸邊界，已經處理完排列的1～n位for(int i=1;i<=n;i++){printf("%d ",P[i]); //輸出當前排列}printf("\n");return;}for(int x=1;x<=n;x++){ //枚舉1～n，試圖將x填入P[index]if(hashTable[x]==false){ //如果x不在P[0]~P[index-1]中P[index]=x; //令P的第index位為x，即把x加入當前排列hashTable[x]=true; //記x已在P中generateP(index+1); //處理排列的第index+1號位hashTable[x]=false; //已處理完P[index]為x的子問題，還原狀態}} } int main(){n=3; //欲輸出1～3的全排列generateP(1); //從P[1]開始填return 0; } //區間貪心 P122 #include<stdio.h> #include<algorithm> using namespace std; const int maxn=110; struct Inteval{int x,y; //開區間左右端點 }I[maxn]; bool cmp(Inteval a,Inteval b){if(a.x!=b.x) return a.x>b.x; //先按左端點從大到小排序else return a.y<b.y; //左端點相同的按右端點從小到大排序 } int main(){int n;while(scanf("%d",&n),n!=0){for(int i=0;i<n;i++){scanf("%d%d",&I[i].x,&I[i].y);}sort(I,I+n,cmp); //把區間排序int ans=1,lastX=I[0].x;for(int i=1;i<n;i++){if(I[i].y<=lastX){lastX=I[i].x;ans++;}}printf("%d\n",ans);} return 0; } //PAT B1040/A1093 有幾個PAT P147 #include<stdio.h> #include<string.h> const int MAXN=10010; const int MOD=1000000007; char str[MAXN]; int leftNumP[MAXN]={}; //每一位左邊（含）P的個數 int main(){gets(str);int len=strlen(str);for(int i=0;i<len;i++){if(i>0) leftNumP[i]=leftNumP[i-1];if(str[i]=='P') leftNumP[i]++;}int ans=0,rightNumT=0; //ans為答案，rightNumT記錄右邊T的個數for(int i=len-1;i>=0;i--){if(str[i]=='T') rightNumT++;else if(str[i]=='A') ans=(ans+leftNumP[i]*rightNumT)%MOD;}printf("%d\n",ans);return 0; } //PAT A1020 Tree Traversals P296 #include<stdio.h> #include<queue> using namespace std; const int maxn=50; struct node{int data;node* lchild;node* rchild; }; int in[maxn],post[maxn]; //中序、后序 int n; //結點個數//返回構建出的二叉樹的根結點地址 node* create(int postL,int postR,int inL,int inR){if(postL>postR) return NULL;node* root=new node;root->data=post[postR];int k;for(k=inL;k<=inR;k++){if(in[k]==post[postR]) break;}int numLeft=k-inL;root->lchild=create(postL,postL+numLeft-1,inL,k-1);root->rchild=create(postL+numLeft,postR-1,k+1,inR);return root; }int num=0; //已輸出的結點個數 void BFS(node* root){queue<node*> q;q.push(root);while(!q.empty()){node* now=q.front();q.pop();printf("%d",now->data);num++;if(num<n) printf(" ");if(now->lchild != NULL) q.push(now->lchild);if(now->rchild != NULL) q.push(now->rchild);} }int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&post[i]);}for(int i=0;i<n;i++){scanf("%d",&in[i]);}node* root=create(0,n-1,0,n-1); //建樹BFS(root); //層序遍歷return 0; } //PAT A1034 Head of a Gang P354 #include<iostream> #include<map> #include<string> using namespace std; const int maxn=2010; //總人數map<int,string> inToString; //編號->姓名 map<string,int> stringToInt; //姓名->編號 map<string,int> Gang; //head->人數 int G[maxn][maxn]={0}, weight[maxn]={0}; //鄰接矩陣G、點權 weight int n,k,numPerson=0; //邊數n、下限k、總人數numPerson bool vis[maxn]={false}; //標記是否被訪問//DFS函數訪問單個連通塊，nowVisit為當前訪問的編號 //head為頭目，numMember為成員編號,totalValue為連通塊的總邊權 void DFS(int nowVisit,int &head,int &numMember,int &totalValue){numMember++; //成員人數加1vis[nowVisit]=true; //標記nowVisit已訪問if(weight[nowVisit]>weight[head]){head=nowVisit; //更新頭目}for(int i=0;i<numPerson;i++){ //枚舉所有人if(G[nowVisit][i]>0){totalValue+=G[nowVisit][i];G[nowVisit][i]=0;G[i][nowVisit]=0;if(vis[i]==false){DFS(i,head,numMember,totalValue);}}} }//DFSTrave函數遍歷整張圖，獲取每個連通塊的信息 void DFSTrave(){for(int i=0;i<numPerson;i++){if(vis[i]==false){int head=i,numMember=0,totalValue=0; //頭目，成員數，總邊權DFS(i,head,numMember,totalValue);if(numMember>2 && totalValue>k){Gang[inToString[head]] = numMember;}}} }//change 函數返回姓名str對應的編號 int change(string str){if(stringToInt.find(str) != stringToInt.end()) return stringToInt[str];else{stringToInt[str]=numPerson;inToString[numPerson]=str;return numPerson++;} }int main(){int w;string str1,str2;cin >> n >> k;for(int i=0;i<n;i++){cin >> str1 >>str2 >> w;int id1=change(str1);int id2=change(str2);weight[id1]+=w;weight[id2]+=w;G[id1][id2]+=w;G[id2][id1]+=w;}DFSTrave(); //遍歷整個圖的所有連通塊，獲取Gang的信息cout << Gang.size() << endl;map<string,int>::iterator it;for(it=Gang.begin();it!=Gang.end();it++){cout << it->first << " " << it->second << endl;}return 0; } //PAT A1076 Forwards on Weibo #include<stdio.h> #include<string.h> #include<queue> #include<vector> using namespace std; const int maxn=1010; struct Node{int id;int layer; }; vector<Node> Adj[maxn]; //鄰接表 bool inq[maxn]={false}; //頂點是否已被加入過隊列int BFS(int s,int L){ //start為起始結點，L為層數上限int numForward=0; //轉發數queue<Node> q;Node start;start.id=s;start.layer=0;q.push(start);inq[start.id]=true;while(!q.empty()){Node topNode=q.front();q.pop();int u=topNode.id;for(int i=0;i<Adj[u].size();i++){Node next=Adj[u][i];next.layer=topNode.layer+1;if(inq[next.id]==false && next.layer<=L){q.push(next);numForward++;inq[next.id]=true;}}}return numForward; }int main(){Node user;int n,L,numFollow,idFollow;scanf("%d%d",&n,&L); //結點個數，層數上限for(int i=1;i<=n;i++){user.id=i;scanf("%d",&numFollow);for(int j=0;j<numFollow;j++){scanf("%d",&idFollow);Adj[idFollow].push_back(user); //邊idFollow->i}}int numQuery,s;scanf("%d",&numQuery); //查詢個數for(int i=0;i<numQuery;i++){memset(inq,false,sizeof(inq)); //inq數組初始化scanf("%d",&s); //起始結點編號int numForward = BFS(s,L);printf("%d\n",numForward);}return 0; } //PAT A1030 Travel Plan P385 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxn=510; const int INF=1000000000;int n,m,st,ed,G[maxn][maxn],cost[maxn][maxn]; int d[maxn],c[maxn],pre[maxn]; bool vis[maxn]={false};void Dijkstra(int s){fill(d,d+maxn,INF);fill(c,c+maxn,INF);for(int i=0;i<n;i++) pre[i]=i;d[s]=0;c[s]=0;for(int i=0;i<n;i++){ //循環n次int u=-1,MIN=INF;for(int j=0;j<n;j++){ //找到未訪問的頂點中d[]最小的if(vis[j]==false && d[j]<MIN){u=j;MIN=d[j];}}//找不到小于INF的d[u]，說明剩下的頂點和起點不連通if(u==-1) return;vis[u]=true;for(int v=0;v<n;v++){if(vis[v]==false && G[u][v]!=INF){if(d[u]+G[u][v]<d[v]){d[v]=d[u]+G[u][v];c[v]=c[u]+cost[u][v];pre[v]=u;}else if(d[u]+G[u][v]==d[v]){if(c[u]+cost[u][v]<c[v]){c[v]=c[u]+cost[u][v];pre[v]=u;}}}}} }void DFS(int v){if(v==st){printf("%d ",v); return;}DFS(pre[v]);printf("%d ",v); }int main(){scanf("%d%d%d%d",&n,&m,&st,&ed);int u,v;fill(G[0],G[0]+maxn*maxn,INF);for(int i=0;i<m;i++){scanf("%d%d",&u,&v);scanf("%d%d",&G[u][v],&cost[u][v]);G[v][u]=G[u][v];cost[v][u]=cost[u][v];}Dijkstra(st);DFS(ed);printf("%d %d\n",d[ed],c[ed]);return 0; }動態規劃
//斐波那契數列 P425 #include<stdio.h> #include<algorithm> using namespace std; const int maxn=1010; int dp[maxn]; int F(int n){if(n==0 || n==1) return 1;if(dp[n]!=-1) return dp[n];else{dp[n]=F(n-1)+F(n-2);return dp[n];}}int main(){fill(dp,dp+maxn,-1);int n;scanf("%d",&n);printf("%d",F(n));return 0; } //數塔問題 P426 #include<stdio.h> #include<algorithm> using namespace std; const int maxn=1010; int dp[maxn][maxn],f[maxn][maxn]; int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){scanf("%d",&f[i][j]); //輸入數塔}}//邊界for(int j=1;j<=n;j++){dp[n][j]=f[n][j];}//從第n-1層不斷向上計算出dp[i][j]for(int i=n-1;i>=1;i--){for(int j=1;j<=i;j++){//狀態轉移方程dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];}}printf("%d",dp[1][1]);return 0; } //最大連續子序列和 P429 #include<stdio.h> #include<algorithm> using namespace std; const int maxn=10010; int dp[maxn],A[maxn]; //A[i]存放序列，dp[i]存放A[i]結尾的連續序列的最大和 int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){ //讀入序列scanf("%d",&A[i]);}//邊界dp[0]=A[0];for(int i=1;i<n;i++){//狀態轉移方程dp[i]=max(dp[i-1]+A[i],A[i]);}int k=0;for(int i=1;i<n;i++){if(dp[i]>dp[k]){k=i;}}printf("%d\n",dp[k]);return 0; } //A1007 Maximum Subsequence Sum PP387 #include<stdio.h> const int maxn=10010; int dp[maxn],A[maxn]; //A[i]存放序列，dp[i]存放A[i]結尾的連續序列的最大和 int s[maxn]={0}; //s[i]表示產生dp[i]的連續序列從A的哪一個元素開始 int main(){int n;bool flag=false; //false表示數組A中全小于0scanf("%d",&n);for(int i=0;i<n;i++){ //讀入序列scanf("%d",&A[i]);if(A[i]>=0) flag=true;}if(flag==false){printf("0 %d %d",A[0],A[n-1]);return 0;}//邊界dp[0]=A[0];for(int i=1;i<n;i++){//狀態轉移方程if(dp[i-1]+A[i] >= A[i]){dp[i]=dp[i-1]+A[i];s[i]=s[i-1];}else{dp[i]=A[i];s[i]=i;}}int k=0;for(int i=1;i<n;i++){if(dp[i]>dp[k]){k=i;}}printf("%d %d %d\n",dp[k],A[s[k]],A[k]);return 0; } //最長不下降子序列（LIS） P432 #include<stdio.h> #include<algorithm> using namespace std; const int N=100; int A[N],dp[N]; int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&A[i]);}int ans=-1;for(int i=1;i<=n;i++){dp[i]=1;for(int j=1;j<i;j++){if(A[j]<=A[i] && dp[j]+1>dp[i]){dp[i]=dp[j]+1;}}ans=max(ans,dp[i]);}printf("%d\n",ans);return 0; } //A1045 Favorite Color Stripe PP390 #include<stdio.h> #include<algorithm> using namespace std; const int maxc=210; //最大顏色數 const int maxn=10010; //最大L int HashTable[maxc]; //將喜歡的顏色序列映射為遞增序列，不喜歡的映射為-1 int A[maxn],dp[maxn];int main(){int n,m,x;scanf("%d%d",&n,&m);fill(HashTable,HashTable+maxc,-1);for(int i=0;i<m;i++){scanf("%d",&x);HashTable[x]=i;}int L,num=0;scanf("%d",&L);for(int i=0;i<L;i++){scanf("%d",&x);if(HashTable[x]>=0){A[num++]=HashTable[x];}}int ans=-1;for(int i=0;i<num;i++){dp[i]=1;for(int j=0;j<i;j++){if(A[j]<=A[i] && dp[i]<dp[j]+1){dp[i]=dp[j]+1;}}ans=max(ans,dp[i]);}printf("%d\n",ans);return 0; } //6 //5 2 3 1 5 6 //12 2 2 4 1 5 5 6 3 1 1 5 6 7 //最長公共子序列（LCS） P434 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int N=100; char A[N],B[N]; int dp[N][N];int main(){gets(A+1); //從下標為1開始讀入gets(B+1);int lenA=strlen(A+1);int lenB=strlen(B+1);//邊界for(int i=0;i<=lenA;i++){dp[i][0]=0;}for(int j=0;j<=lenB;j++){dp[0][j]=0;}//狀態轉移方程for(int i=1;i<=lenA;i++){for(int j=1;j<=lenB;j++){if(A[i]==B[j]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}printf("%d\n",dp[lenA][lenB]);return 0; } //sadstory //adminisorry 6 //A1045 Favorite Color Stripe PP392 #include<stdio.h> #include<algorithm> using namespace std; const int maxc=210; //最大顏色數 const int maxn=10010; //最大L int A[maxc],B[maxn],dp[maxc][maxn];int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d",&A[i]);}int L;scanf("%d",&L);for(int i=1;i<=L;i++){scanf("%d",&B[i]);}//邊界for(int i=0;i<=m;i++){dp[i][0]=0;}for(int j=0;j<=L;j++){dp[0][j]=0;}//狀態轉移方程for(int i=1;i<=m;i++){for(int j=1;j<=L;j++){int MAX=max(dp[i-1][j],dp[i][j-1]);if(A[i]==B[j]){dp[i][j]=MAX+1;}else{dp[i][j]=MAX;}}}printf("%d\n",dp[m][L]);return 0; } //6 //5 2 3 1 5 6 //12 2 2 4 1 5 5 6 3 1 1 5 6 7 //A1040 Longest Symmetric String(最長回文子串) P394 #include<stdio.h> #include<string.h> const int maxn=1010; char S[maxn]; int dp[maxn][maxn]; int main(){gets(S);int len=strlen(S),ans=1; //ans為最長回文子串的長度memset(dp,0,sizeof(dp));//邊界for(int i=0;i<len;i++){dp[i][i]=1;if(i<len-1){if(S[i]==S[i+1]){dp[i][i+1]=1;ans=2;} }}//狀態轉移方程for(int L=3;L<=len;L++){ //枚舉子串的長度for(int i=0;i+L-1<len;i++){ //枚舉子串的起始端點int j=i+L-1; //子串的右端點if(S[i]==S[j] && dp[i+1][j-1]==1){dp[i][j]=1;ans=L;}}}printf("%d\n",ans);return 0; } //Is PAT&TAP symmetric? 11 //A1068 Find More Coins(背包問題) PP396 #include<stdio.h> #include<algorithm> using namespace std; const int maxn=10010; const int maxv=110; int w[maxn],dp[maxv]; int choice[maxn][maxv]; int flag[maxn]; bool cmp(int a,int b){return a>b; } int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&w[i]);}sort(w+1,w+n+1,cmp); //逆序排列//邊界for(int i=0;i<=m;i++){dp[i]=0;}//狀態轉移方程for(int i=1;i<=n;i++){for(int v=m;v>=w[i];v--){if(dp[v]<=dp[v-w[i]]+w[i]){dp[v]=dp[v-w[i]]+w[i];choice[i][v]=1; //放入第i件物品}else{choice[i][v]=0; //不放第i件物品}}}if(dp[m]!=m){printf("No Solution"); //無解}else{//記錄最優路徑int k=n,v=m,num=0;while(k>=0){if(choice[k][v]==1){flag[k]=1;v-=w[k];num++;}else{flag[k]=0;}k--;}//輸出方案for(int i=n;i>=1;i--){if(flag[i]==1){printf("%d",w[i]);num--;if(num>0) printf(" ");}}}return 0; }總結
以上是生活随笔為你收集整理的C与C++ 算法笔记中的代码的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 用OPENCV视觉解数独
- 下一篇： 2018.11.6