请问360 如何买粉笔啊 --各位大圣指点一下

贪心过了90

#include <iostream> #include <vector> using namespace std; int a, b, c, d; int x, y, z; int main(){ int n, m; while(cin >> n >> m){ cin >> a >> b >> c >> d; cin >> x >> y >> z; vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0)); for(int i = 0; i <= n; ++i){ for(int j = 0; j <= m; ++j){ if(i >= a && j >= b) dp[i][j] = max(dp[i][j], dp[i - a][j - b] + x); if(i >= d){ dp[i][j] = max(dp[i][j], dp[i - d][j] + z); } if(j >= c){ dp[i][j] = max(dp[i][j], dp[i][j - c] + y); } } } cout << dp[n][m] << endl; } return 0; }

暴力，组合粉笔0-min(n/a,m/b)，加剩下的粉笔。100%

我是这样做的: dp[][]：表示i个彩色，j个白色的最大价值 dp[i][i] = Max(只取彩色，只取白色，白+彩色)

求最大的，一看就知道是动态规划，虽然我不会写

一、优先纯色的 二、优先混合的 三、取两者最大

贪心，算法三种情况粉笔单价，按单价高低分别按顺序卖就行O（1）

第二题插入 80

贪心90

这题注意中间价格要double吧

#include<iostream> #include<vector> using namespace std; int main() { int n, m; cin >> n >> m; int a, b, c, d; cin >> a >> b >> c >> d; int x, y, z; cin >> x >> y >> z; vector<vector<int>>mark(n + 1, vector<int>(m + 1, -1)); mark[n][m] = 0; for(int i=n;i>=0;--i) for (int j = m; j >=0; --j) { if (mark[i][j] != -1) { if (i >= a&&j >= b) mark[i - a][j - b] = mark[i][j] + x; if (j >= c) mark[i][j - c] = mark[i][j] + y; if (i >= d) mark[i - d][j] = mark[i][j] + z; } } int result = 0; for (int i = 0; i <= n; ++i) for (int j = 0; j <= m; ++j) if (mark[i][j] > result) result = mark[i][j]; cout << result; }

深搜暴力破解超时，只有40%，哭了。 第二题也超时，80%，又哭了。

枚举前两种个数，就好了，大约1e6

我直接暴力穷举A了 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int a = in.nextInt(); int b = in.nextInt(); int c = in.nextInt(); int d = in.nextInt(); int x = in.nextInt(); int y = in.nextInt(); int z = in.nextInt(); int max = 0; int nowN = n; int nowM = m; for(int i=0;i<=n/d;i++) { nowN = n - (d * i); for(int j=0;j<=m/c;j++) { nowM = m - (c * j); int price = (z * i) + (y * j) + (Math.min(nowM/b, nowN/a) * x); if(price > max) { max = price; } } } System.out.println(max); } }

三个for循环，注意判断边界，然后就过了。。但是第二题怎么做都超时，希望有人贴一下解法！ import java.util.*; public class Main{ public void process(){ Scanner sc = new Scanner(System.in); String pen; String box; String price; String[] penStArr; String[] boxStArr; String[] priceStArr; int colorPen; int whitePen; int colorA; int whiteB; int whiteC; int colorD; int x; int y; int z; int sum1; int sum2; int sum3; while(sc.hasNext()){ pen = sc.nextLine(); box = sc.nextLine(); price = sc.nextLine(); colorPen = Integer.parseInt(pen.split(" ")[0]); whitePen = Integer.parseInt(pen.split(" ")[1]); colorA = Integer.parseInt(box.split(" ")[0]); whiteB = Integer.parseInt(box.split(" ")[1]); whiteC = Integer.parseInt(box.split(" ")[2]); colorD = Integer.parseInt(box.split(" ")[3]); x = Integer.parseInt(price.split(" ")[0]); y = Integer.parseInt(price.split(" ")[1]); z = Integer.parseInt(price.split(" ")[2]); int bound1 = colorPen/colorD; int bound2 = whitePen/whiteC; int bound3 = (colorPen/colorA > whitePen/whiteB)? whitePen/whiteB : colorPen/colorA; int finalSum = 0; int tempSum = 0; for(int i = 0; i<= bound1; i++){ for(int j = 0; j<= bound2; j++){ for(int m = 0; m<= bound3; m++){ if((i*colorD + m*colorA) > colorPen || (j*whiteC+m*whiteB) > whitePen){ break; } tempSum = i*z + j*y + m*x; finalSum = tempSum > finalSum ? tempSum : finalSum; } } } System.out.println(finalSum); } } public static void main(String[] args){ Main m = new Main(); m.process(); } }

直接排列组合

题目有坑,粉白中间错开靠，n粉 m白，a粉，b白，a+b -> x，c白, c->y，d粉, d->z 算 粉 单卖单价 z / d, 白 单卖单价 y / c, 比较 x 和 a * 粉单价 + b * 白单价，x大就优先捆绑卖，否则优先单个卖，贪心

贪心搞一下就好了

过了80%

用奥数方法AC了