都是细节处理，就直接放在一篇博客里了
游戏智商
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
熊的智商高还是猴子的智商高，这或许是一个很难考究的问题。故事里，吉吉国王一直标榜自己是最聪明最伟大的猴子国王，他的毛毛也是这么坚信。而我们的熊大和熊二却一直相信他们熊熊才是最聪明的。于是，在导游光头强的建议下，他们决定来一场 pk。
Pk 的内容是这样的，有 n 个格子，每个格子从左到右的编号依次是 1 到 n（编号也是位置)，每个格子上都有不同美味值的水果（猴子们和熊们都很喜欢吃水果，所以水果对他们来说很有吸引力）。他们从位置 0 开始出发，手上有 AB 两种卡片，A 卡有 na 张，B 卡片有nb 张。每次他们可以用掉一张卡片，然后往前跳若干格，跳的格子数就是卡片上的数字。每跳到一个格子上，就可以吃掉对应格子里面的水果，获得水果的美味值。当然了，我们会保证当卡片用完的时候，一定刚好跳到第 n 个格子上。卡片一定要用完，不能有剩余。
游戏的结果就是在相同的情况下，谁能获得的水果美味值总和最大。熊熊们想要赢得这个比赛，于是熊二请求你的帮助。如果你可以帮助他算出最大值，他甚至可以把他最心爱的蜂蜜分享给你。
输入
输入第一行是3个整数n，na，nb,va,vb，n表示格子的总数，na表示A种卡片的数量，nb表示B种卡片的数量，va表示A种卡片上的数，vb表示B种卡片上的数。保证n一定等于nava+nbvb。
接下来n个整数，表示每个格子上水果的美味值，注意美味值有可能是负数。
输出
输出只有一行一个整数，表示卡片用完的时候，最多可以得到的美味值总和。
样例输入 Copy
3 1 1 2 1
1 2 3
样例输出 Copy
5
提示
共计有20个测试点。
对于第1-6个测试点，保证na=1,nb<=200，美味值都是小于等于10000的正整数。
对于第7-12个测试点，保证1<=na,nb<=12，美味值的绝对值小于等于10000。
对于100%的数据，保证1<=n<=20000,1<=na,nb<=2000,1<=va,vb<=5，va不等于vb，美味值的绝对值不超过1000000。
思路：
dp[i][j]表示用了i张A卡片和j张B卡片所获取的美味值的最大值，状态转移方程：
dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i*va+j*vb]); dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i*va+j*vb]);
注意一下细节处理
开始数组开小了一直TLE 就离谱
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; #define I_int ll #define inf 0x3f3f3f3f inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=2010; ll dp[maxn][maxn]; ///dp[i][j]表示用了i张A卡片和j张B卡片所获取的美味值的最大值 ll n,na,nb,va,vb; ll a[20010]; void AC(){ n=read();na=read();nb=read();va=read();vb=read(); for(ll i=1;i<=n;i++) a[i]=read(); for(ll i=0;i<=na;i++){ for(ll j=0;j<=nb;j++){ if(i>=1) dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i*va+j*vb]); if(j>=1) dp[i][j]=max(dp[i][j],dp[i][j-1]+a[i*va+j*vb]); } } out(dp[na][nb]); } int main(){ AC(); return 0; }
路标
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
一天，小Z到OI总部旅游，发现OI总部相当庞大，因此小Z常常迷路。本着“为人民服务”的原则，小Z决定为OI总部制作路标。OI总部由n个OI讨论社组成，有些OI讨论社间有路相连，路是无向的。小Z要在每个OI讨论社竖一个路标。小Z是一个喜欢标新立异的人，他制作的路标分两种：黑路标和白路标。小Z规定：与白路标有路相连的必须是黑路标。由于制作白路标比较省钱，所以他想知道最多有几个OI讨论社的路标为白路标。（注意：OI总部不一定是连通图。）
输入
第一行包括2个整数m和n，表示路的条数和OI讨论社的个数。
接下来的m行，每行两个正整数x和y（x,y<=n且x≠y），表示第x个OI讨论社与第y个OI讨论社有路相连。
输出
共一行，包括1个正整数ans，表示最多有几个OI讨论社的路标为白路标。
样例输入 Copy
1 2
1 2
样例输出 Copy
1
提示
20%数据：n<=3
另有20%数据：m<=3
100%的数据满足：1<=n<=10
思路：
数据范围很小，直接dfs就行，要注意看清题目中说的是白块只能和黑块相连，而黑块则不受限制
读错题wa了5发
#include<bits/stdc++.h> using namespace std; const int maxn=110; int maxx=-1; int g[maxn][maxn],col[maxn]; int n,m; ///1是白2是黑 bool check(int u){ for(int i=1;i<=n;i++) if(g[u][i]||g[i][u]){ if(col[i]==1&&col[u]==1) return 0; } return 1; } void dfs(int u){ if(u==n+1){ int tot=0; for(int i=1;i<=n;i++) if(col[i]==1) tot++; maxx=max(maxx,tot); } else{ for(int i=1;i<=2;i++){ col[u]=i; if(check(u)) dfs(u+1); col[u]=0; } } } void AC(){ cin>>m>>n; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; g[x][y]=g[y][x]=1; } dfs(1); cout<<maxx<<endl; } int main(){ AC(); return 0; }
