回溯贪心

回溯
P1036 [NOIP 2002 普及组] 选数 
#include <bits/stdc++.h>

using namespace std;

int n,m,cnt;
int a[21];

void dfs(int w,int start,int sum){ 
    if (w == m){ 
        bool y=1; 
        for(int i=2;i<=sqrt(sum);i++){ 
        if(sum%i==0){
        y=0;
        break; 
}
}
if(y) cnt++;
        
        return; 
    }
    for(int i=start+1;i<n;i++){ 
        dfs(w+1,i,sum+a[i]); 
    }
}

int main(){
cin >> n >> m; 

for(int i=0;i<n;i++) cin>>a[i]; 

dfs(0,-1,0);
cout << cnt; 

    return 0; 
}
    
P1706 全排列问题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<iomanip>
#include <algorithm>
#include<cmath>
#include<vector>
#include<set>
using namespace std;
int a[10];
int main()
{
int n,i,j=1,k;
cin>>n;
for(i=1;i<=n;i++)
 {a[i]=n-i+1;j*=i;}
for(i=1;i<=j;i++)
 {next_permutation(a+1,a+n+1);
  for(k=1;k<=n;k++)
   cout<<"    "<<a[k];
       
  cout<<endl;
 }
 return 0;
}
贪心算法：
P1208 [USACO1.3] 混合牛奶 Mixing Milk
#include <bits/stdc++.h>

using namespace std;
const int maxn=2000000+5;

struct cow{
int p,a;
cow(int p=0,int a=0): p(p),a(a){}
}milk[maxn];

bool cmp(const cow &a,const cow &b)
{
   return a.p<b.p;
}
int main (){
int n,m,dj;
cin>>n>>m;
for (int i=0;i<m;i++){
cin>>milk[i].p>>milk[i].a;
}
sort(milk,milk+m,cmp);
int tot=0,sum=0;
for (int i=0;i<m;i++){
if (tot+milk[i].a<=n) {
tot+=milk[i].a;
sum+=milk[i].p*milk[i].a;
}
else {
sum+=(n-tot)*milk[i].p;
break;
}
}
cout<<sum;
return 0;
}

P1650 田忌赛马 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=2001;
int a[N],b[N],dp[N][N];

bool Cmp(int x,int y) {return x>y;}

int main()
{
int n,i,j; scanf("%d",&n);
for (i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) scanf("%d",&b[i]);
sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (a[i]>b[j]) dp[i][j]=max(dp[i-1][j-1]+200,max(dp[i-1][j]-200,dp[i][j-1]-200));
else if (a[i]==b[j]) dp[i][j]=max(dp[i-1][j-1],max(dp[i-1][j]-200,dp[i][j-1]-200));
 else dp[i][j]=max(dp[i-1][j]-200,dp[i][j-1]-200);
printf("%d\n",dp[n][n]);
return 0;
}

P1181 数列分段 Section I 
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[100002],ans;
int main(){
    scanf("%d%d",&n,&m);ans=n+1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]+a[i-1]<=m)a[i]+=a[i-1],ans--;
    }
    printf("%d\n",ans);
    return 0;
}

P1094 [NOIP 2007 普及组] 纪念品分组 
#include<bits/stdc++.h>
using namespace std;
int W,ans=0;
int n,a[30001];
int l,r,i;
int main()
{
    scanf("%d%d",&W,&n);
    for(i=1;i<=n;i++)
      scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    l=1;  r=n;
    while(l<=r)
    {
        if(a[l]+a[r]<=W)   
          l++,r--,ans++;
        else
          r--,ans++;  
    }
    printf("%d",ans);
    return 0;
}
P1090 [NOIP 2004 提高组] 合并果子
#include <cstdio>
#include <queue>
using std :: priority_queue;
using std :: greater;
using std :: vector;

int n, ans = 0;
priority_queue < int, vector <int>, greater <int> > q;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
int x; scanf("%d", &x);
q.push(x);
}
while(q.size() > 1)
{
int x = q.top(); q.pop();
int y = q.top(); q.pop();
ans += x + y;
q.push(x + y);
}
printf("%d\n", ans);
return 0;
}