题目链接：
http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=701
1001 ：
矩阵快速幂
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<queue>
#include<vector>
using namespace std;
const int N = 5e5+, M = 1e2+, mod = ,inf = 1e9;
typedef long long ll;
struct Matix {
ll arr[M][M];
};
ll x,m,k,c;
Matix mul(Matix a,Matix b,ll hang ,ll lie) {
Matix ans;
memset(ans.arr,,sizeof(ans.arr));
for(int i=;i<=hang;i++) {
for(int t=;t<=lie;t++)
for(int j=;j<=lie;j++) {
ans.arr[i][t]+=(a.arr[i][j]*b.arr[j][t]);
ans.arr[i][t]%=k;
}
}
return ans;
}
Matix pow(Matix ans,Matix a,ll x) {
while(x) {
if(x&) ans=mul(ans,a,,);
a=mul(a,a,,);
x/=;
}
return ans;
}
int main(){
ll x,y,z;
int T,cas=;
scanf("%d",&T);
while(T--) {
scanf("%I64d%I64d%I64d%I64d",&x,&m,&k,&c);
Matix fir,sec;
Matix now;
now.arr[][]=x;
now.arr[][]=x;
memset(fir.arr,,sizeof(fir.arr));
sec.arr[][]=;sec.arr[][]=;
sec.arr[][]=;sec.arr[][]=;
fir.arr[][]=;
fir.arr[][]=;
fir=pow(fir,sec,m-);fir=mul(now,fir,,);
printf("Case #%d:\n",cas++);
if(fir.arr[][]==c)puts("Yes");
else puts("No");
}
return ;
}
1002：
状态压缩DP
我们设定dp[1<<16][16]：dp[i][j]：i为当前选取的状态并以第j个数结尾的最大值，那么答案就是 max{dp[全集][k]} k属于0到n-1
对于dp[i][j] ， i这个状态已经填了x个数，我们准备填第x+1个数时， 如果当前x+1位置必填某个数，那么 就只更新以规定的这个数结尾转移方程
如果没有那就 枚举那么可以任意放的数来更新相应的状态及答案
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<queue>
#include<vector>
using namespace std;
const int N = <<, M = 1e6+, mod = ,inf = 1e9;
typedef long long ll; ll dp[<<][];
int n,a[N],p[N],H[N],F[N];
int main() {
int T,cas = ;
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
memset(H,,sizeof(H));
memset(F,-,sizeof(F));
int tmp = ;
for(int i=;i<n;i++) {
scanf("%d%d",&a[i],&p[i]);
if(p[i]!=-)
H[i] = ,F[p[i]] = i;
}
for(int i=;i<(<<n);i++)
for(int j=;j<n;j++) dp[i][j] = -1e18;
// for(int i=0;i<n;i++)
// for(int j=0;j<n;j++) if(i!=j&&!H[i]&&!H[j]) dp[(1<<i)|(1<<j)][j] = a[i]*a[j], dp[(1<<i)|(1<<j)][i] = a[i]*a[j];
if(F[]!=-) dp[(<<F[])][F[]] = ;
else {
for(int i=;i<n;i++) {
if(!H[i]) dp[(<<i)][i] = ;
}
}
int U = (<<n) - ;
for(int i=;i<=U;i++) {
int counts = ;
for(int j=;j<n;j++) if((<<j)&(i)) counts++;
if(F[counts]!=-) {
counts = F[counts];
for(int j=;j<n;j++) if(i&(<<j)&&counts!=j)dp[i|(<<(counts))][counts] = max(dp[i][j]+a[j]*a[counts],dp[i|(<<counts)][counts]);
}
else {
for(int k=;k<n;k++) {
if((<<k)&(i))
for(int j=;j<n;j++) {
if(!((<<j)&i)) {
dp[i|(<<j)][j] = max(dp[i|(<<j)][j],dp[i][k]+a[k]*a[j]);
}
}
}
}
}
printf("Case #%d:\n",cas++);
ll ans = -1e18;
for(int i=;i<n;i++) ans = max(dp[U][i],ans) ;
printf("%I64d\n",ans);
}
return ;
}
1004：D Game
区间dp
设定dp[i][j]为i到j这个区间的最大答案，每次去选择连续不连续的2个/3个去删除，暴力转移就好
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<map>
using namespace std;
const int N = , M = , mod = 1e9 + , inf = 0x3f3f3f3f;
typedef long long ll; int dp[N][N];
ll a[N],d;
map<ll,int > mp;
int dfs(int l,int r) {
if(dp[l][r]!=-) return dp[l][r];
int& ret = dp[l][r];
ret = ;
if(l>=r) return ret; if(l+==r) {
if(mp[a[r]-a[l]]) return (ret = );
else return (ret = );
} int tmp = ;
if(mp[a[r]-a[l]]) tmp+=;// cout<<a[r]-a[l]<<endl;
if(dfs(l+,r-)==((r-)-(l+)+)) ret = tmp+((r-)-(l+)+);
if(abs(a[r]-a[l])%==&&mp[(a[r]-a[l])/])
for(int i=l+;i<r;i++) {
tmp = ;
if(a[r]-a[i]==a[i]-a[l]&&mp[a[i]-a[l]]) {
tmp = ;
}
else continue;
if(tmp+dfs(l+,i-)+dfs(i+,r-)==r-l+) {
ret = r-l+;break;
}
} for(int i=l+;i<r;i++) {
ret = max(ret,dfs(l,i)+dfs(i+,r));
}
return ret;
}
int main() {
int T,m,n;
scanf("%d",&T);
while(T--) {
mp.clear();
memset(dp,-,sizeof(dp));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%I64d",&a[i]);
for(int i=;i<=m;i++) scanf("%I64d",&d),mp[d] = ;
printf("%d\n",dfs(,n));
}
return ;
} /*
1
7 2
1 5 8 101 59 62 201
100 3
*/
1005：
预处理+dfs
预处理每种长度，每种长度的答案
再对对应长度dfs求出答案
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<queue>
#include<vector>
using namespace std;
const int N = 1e3+, M = 1e6+, mod = ,inf = 1e9;
typedef long long ll; ll len[N],dp[N],L,R;
ll dfs(ll x){
if(x<=) return ;
if(x<=) return x;
if(x==) return ;
ll ans=;
int pos = upper_bound(len+,len+,x) - len - ;
if(len[pos]==x) return dp[pos];
if(x-len[pos]==) return dp[pos]+;
ll ret = dp[pos]+;
ll shen = x-len[pos]-;
return ret+shen - dp[pos] + dfs(len[pos] - shen);
}
int main() {
dp[] = ;
len[] = ;
for(int i=;i<=;i++) {
len[i] = len[i-]*+;
}
for(int i=;i<=;i++) {
dp[i] = dp[i-] + + len[i-] - dp[i-];
}
int T;
scanf("%d",&T);
while(T--) {
scanf("%I64d%I64d",&L,&R);
printf("%I64d\n",dfs(R)-dfs(L-));
}
return ;
}
1006
优先队列
首先按照拓扑，将入度为0的压入，优先位置大的放前面。。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include<queue>
#include<vector>
using namespace std;
const int N = 5e5+, M = 1e6+, mod = ,inf = 1e9;
typedef long long ll; int k,c,x,d[N],n,m,vis[N];
vector<int >G[N]; int ans[N];
int main() {
int T;
int cas = ;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) G[i].clear();
for(int i=;i<=n;i++) vis[i] = ,d[i] = ;
for(int i=;i<=m;i++) {
int a,b;
scanf("%d%d",&a,&b);
G[a].push_back(b);
d[b]++;
}
priority_queue<int > q; for(int i=;i<=n;i++) {
if(d[i]==) q.push(i);
}
int cnt = ;
while(!q.empty()) {
int k = q.top();
ans[++cnt] = k;
// cout<<k<<endl;
q.pop();
for(int i=;i<G[k].size();i++) {
d[G[k][i]]--;
if(d[G[k][i]]==&&!vis[G[k][i]]) {
q.push(G[k][i]); vis[G[k][i]] = ;
}
}
}
int mi = 1e9;
ll aa = ;
for(int i=;i<=cnt;i++) {
mi = min(ans[i],mi);
aa = aa + mi;
}
printf("%I64d\n",aa);
}
return ;
}